A Provably Secure Group Signature Scheme from Code-Based Assumptions

DOI10.1007/978-3-662-48797-6_12zbMATH Open1396.94075arXiv1909.04472OpenAlexW2254971601MaRDI QIDQ2811134FDOQ2811134

Huaxiong Wang, Martianus Frederic Ezerman, San Ling, Hoa Nguyen, Hyung Tae Lee

Publication date: 10 June 2016

Published in: Advances in Cryptology -- ASIACRYPT 2015 (Search for Journal in Brave)

Abstract: We solve an open question in code-based cryptography by introducing two provably secure group signature schemes from code-based assumptions. Our basic 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. The construction produces smaller key and signature sizes than the previous group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed $2^{24}$, which is roughly comparable to the current population of the Netherlands. We develop the basic scheme further to achieve the strongest anonymity notion, i.e., CCA-anonymity, with a small overhead in terms of efficiency. The feasibility of two proposed schemes is supported by implementation results. Our two schemes are the first in their respective classes of provably secure groups signature schemes. Additionally, the techniques introduced in this work might be of independent interest. These are a new verifiable encryption protocol for the randomized McEliece encryption and a novel approach to design formal security reductions from the Syndrome Decoding problem.

Full work available at URL: https://arxiv.org/abs/1909.04472

Mathematics Subject Classification ID

Cryptography (94A60)

Cited In (22)

• A code-based signature scheme from the Lyubashevsky framework
• A scalable post-quantum hash-based group signature
• Post-quantum secure fully-dynamic logarithmic-size deniable group signature in code-based setting
• Zero-knowledge arguments for matrix-vector relations and lattice-based group encryption
• Group encryption: full dynamicity, message filtering and code-based instantiation
• Group encryption: full dynamicity, message filtering and code-based instantiation
• Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions
• A rank metric code-based group signature scheme
• Group signatures and more from isogenies and lattices: generic, simple, and efficient
• Group signatures and more from isogenies and lattices: generic, simple, and efficient
• Zero-Knowledge Arguments for Matrix-Vector Relations and Lattice-Based Group Encryption
• Fully dynamic attribute-based signatures for circuits from codes
• Provably Secure Group Signature Schemes From Code-Based Assumptions
• Efficient code-based fully dynamic group signature scheme
• A Practical Group Signature Scheme Based on Rank Metric
• Short code-based one-out-of-many proofs and applications
• Code-Based Zero Knowledge PRF Arguments
• A New Dynamic Code-Based Group Signature Scheme
• A Lattice-Based Group Signature Scheme with Message-Dependent Opening
• Zero-knowledge arguments for lattice-based accumulators: logarithmic-size ring signatures and group signatures without trapdoors
• A code-based group signature scheme
• Code-based signatures from new proofs of knowledge for the syndrome decoding problem

This page was built for publication: A Provably Secure Group Signature Scheme from Code-Based Assumptions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2811134)