Cryptology ePrint Archive: Report 2015/479

A Provably Secure Group Signature Scheme from Code-Based Assumptions

Martianus Frederic Ezerman and Hyung Tae Lee and San Ling and Khoa Nguyen and Huaxiong Wang

Abstract: We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the scheme satisfies the CPA-anonymity and traceability requirements in the random oracle model, assuming the hardness of the McEliece problem, the Learning Parity with Noise problem, and a variant of the Syndrome Decoding problem. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands ($\approx 2^{24}$ users). The feasibility of the scheme is supported by implementation results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.

Category / Keywords: code-based cryptography, group signatures, zero-knowledge protocols, McEliece encryption, syndrome decoding

Date: received 20 May 2015, last revised 27 Aug 2015

Contact author: khoantt at ntu edu sg

Available format(s): PDF | BibTeX Citation

Version: 20150827:094615 (All versions of this report)

Short URL: ia.cr/2015/479

Discussion forum: Show discussion | Start new discussion