A Code-based Group Signature Scheme from the Schnorr-Lyubashevsky Framework

Abstract

Code-based group signatures are a promising candidate for post-quantum cryptography, but existing code-based group signature schemes struggle with the challenges of large signature sizes caused by zero-knowledge proofs. To address this issue, we propose a novel and practical code-based group signature scheme built upon the Schnorr-Lyubashevsky paradigm. Our construction achieves constant-size signatures and public keys, independent of the group cardinality, and its security is formally proven in the random oracle model under the hardness assumptions of the Syndrome Decoding (SD) and Decoding One Out of Many (DOOM) problems. To alleviate the performance bottleneck of rejection sampling, we design and implement a batch processing optimization for the signing algorithm, which significantly accelerates signature generation by applying vectorization to the most computationally intensive operations. Experimental results show that the optimization renders signing practical. Our scheme features the most compact signature size among existing codebased group signature schemes. All related code is open-sourced and available at https://github.com/Latters/CodeBasedGroupSig/.