NDLI: A code-based group signature scheme

Content Provider	Springer Nature Link
Author	Gaborit, Philippe Blazy, Olivier Cauchie, Stéphane Alamélou, Quentin
Copyright Year	2016
Abstract	This work is the extended version of Alamélou et al. (in: Tillich et al. (eds.) The 9th International workshop on coding and cryptography 2015 (WCC2015), 2015) which proposed the first code-based group signature. 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 et al. (in: Cachin and Camenisch (eds.) Advances in cryptology—EUROCRYPT 2004, 2004) (KTY model) while handling membership revocation. Our security is based on a relaxation of the model of Bellare et al. (in: Topics in cryptology—CT-RSA 2005, 2005) (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 different 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 applications, we consider the case of the code-based CFS signature scheme (Nicolas in Advances in cryptology—ASIACRYPT 2001, 2001) 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 (Alamélou et al. in: Tillich et al. (eds.) The 9th international workshop on coding and cryptography 2015 (WCC2015), 2015). 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 (Berlekamp et al. in IEEE Trans Inf Theory 24(3):384–386, 1978).
Ending Page	493
Page Count	25
Starting Page	469
File Format	PDF
ISSN	09251022
e-ISSN	15737586
Journal	Designs, Codes and Cryptography
Issue Number	1-2
Volume Number	82
Language	English
Publisher	Springer US
Publisher Date	2016-09-28
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Code-based cryptography Information and Communication, Circuits Data Structures, Cryptology and Information Theory Proof of knowledge Random oracle model Discrete Mathematics in Computer Science Data Encryption Coding and Information Theory Cryptography Combinatorics Quantum cryptography Group signature
Content Type	Text
Resource Type	Article
Subject	Applied Mathematics Discrete Mathematics and Combinatorics Theoretical Computer Science Computer Science Applications

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Zero-knowledge proofs of knowledge for group homomorphisms

An efficient IBE scheme with tight security reduction in the random oracle model

The random oracle model: a twenty-year retrospective

Policy-based signature scheme from lattices

Distributed Ring Signatures from General Dual Access Structures

Efficient public key encryption with smallest ciphertext expansion from factoring

Extended security arguments for signature schemes

Comparing two pairing-based aggregate signature schemes

Efficient discrete logarithm based multi-signature scheme in the plain public key model

A code-based group signature scheme

Similar Documents

Zero-knowledge proofs of knowledge for group homomorphisms

An efficient IBE scheme with tight security reduction in the random oracle model

The random oracle model: a twenty-year retrospective

Policy-based signature scheme from lattices

Distributed Ring Signatures from General Dual Access Structures

Efficient public key encryption with smallest ciphertext expansion from factoring

Extended security arguments for signature schemes

Comparing two pairing-based aggregate signature schemes

Efficient discrete logarithm based multi-signature scheme in the plain public key model

A code-based group signature scheme