Paper 2016/1119
A Code-Based Group Signature Scheme
Quentin Alamélou, Olivier Blazy, 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
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Published elsewhere. Minor revision. to appear in DCC
- Keywords
- code based cryptogroup signature
- Contact author(s)
- gaborit @ unilim fr
- History
- 2016-12-01: received
- Short URL
- https://ia.cr/2016/1119
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2016/1119, author = {Quentin Alamélou and Olivier Blazy and Stéphane Cauchie and Philippe Gaborit}, title = {A Code-Based Group Signature Scheme}, howpublished = {Cryptology {ePrint} Archive, Paper 2016/1119}, year = {2016}, url = {https://eprint.iacr.org/2016/1119} }