Paper 2015/479

A Provably Secure Group Signature Scheme from Code-Based Assumptions

Martianus Frederic Ezerman, Hyung Tae Lee, San Ling, 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.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in ASIACRYPT 2015
Keywords
code-based cryptographygroup signatureszero-knowledge protocolsMcEliece encryptionsyndrome decoding
Contact author(s)
khoantt @ ntu edu sg
History
2015-12-05: last of 2 revisions
2015-05-20: received
See all versions
Short URL
https://ia.cr/2015/479
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/479,
      author = {Martianus Frederic Ezerman and Hyung Tae Lee and San Ling and Khoa Nguyen and Huaxiong Wang},
      title = {A Provably Secure Group Signature Scheme from Code-Based Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2015/479},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/479}},
      url = {https://eprint.iacr.org/2015/479}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.