Cryptology ePrint Archive: Report 2016/1119
A Code-Based Group Signature Scheme
Quentin Alamélou and Olivier Blazy and Stéphane Cauchie and Philippe Gaborit
Abstract: This work is the extended version of [1] which proposed the first code-based group sig-
nature. The new group signature scheme we present here has numerous advantages over all
existing post-quantum constructions and even competes (in terms of properties) with pairing
based constructions: it allows to add new members during the lifetime of the group (dynamic).
Plus, it appears that our scheme might be extended into a traceable signature according to the
definition of Kiayias, Tsiounis and Yung [2] (KTY model) while handling membership revo-
cation. Our security is based on a relaxation of the model of Bellare, Shi and Zhang [3] (BSZ
model) verifying the properties of anonymity, traceability and non-frameability. The main idea
of our scheme consists in building an offset collision of two syndromes associated to two dif-
ferent matrices: a random one which enables to build a random syndrome from a chosen small
weight vector; and a trapdoor matrix for the syndrome decoding problem, which permits to find
a small weight preimage of the previous random syndrome to which a fixed syndrome is added.
These two small weight vectors will constitute the group member’s secret signing key whose
knowledge will be proved thanks to a variation of Stern’s authentication protocol. For appli-
cations, we consider the case of the code-based CFS signature scheme [4] of Courtois, Finiasz
and Sendrier. If one denotes by N the number of group members, CFS leads to signatures and
public keys sizes in $N^{1/\sqrt{\log N}}$. Along with this work, we also introduce a new kind of proof of knowledge, Testable weak Zero Knowledge (TwZK), implicitly covered in the short version of this paper [1]. TwZK proofs appear particularly well fitted in the context of group signature schemes: it allows a verifier to test whether a specific witness is used without learning anything more from the proof. Under the Random Oracle Model (ROM), we ensure the security of our scheme by defining the One More Syndrome Decoding problem, a new code-based problem related to the Syndrome Decoding problem [5].
Category / Keywords: public-key cryptography / code based crypto, group signature
Original Publication (with minor differences): to appear in DCC
Date: received 17 Nov 2016, last revised 30 Nov 2016
Contact author: gaborit at unilim fr
Available format(s): PDF | BibTeX Citation
Version: 20161201:045426 (All versions of this report)
Short URL: ia.cr/2016/1119
[ Cryptology ePrint archive ]