A provably secure group signature scheme from code-based assumptions

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

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contributionpeer-review

23 Citations (Scopus)

Abstract

We solve an open question in code-based cryptography by introducing the first provably secure group signature scheme from code-based assumptions. Specifically, the 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. Our construction produces smaller key and signature sizes than the existing post-quantum group signature schemes from lattices, as long as the cardinality of the underlying group does not exceed the population of the Netherlands (≈224 users). The feasibility of the scheme is supported by implementation results. Additionally, the techniques introduced in this work might be of independent interest: a new verifiable encryption protocol for the randomized McEliece encryption and a new approach to design formal security reductions from the Syndrome Decoding problem.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2015
Subtitle of host publication21st International Conference on the Theory and Application of Cryptology and Information Security, Auckland, New Zealand, November 29 - December 3, 2015, Proceedings. Part I
EditorsTetsu Iwata, Jung Hee Cheon
Place of PublicationHeidelberg
PublisherSpringer, Springer Nature
Pages260-285
Number of pages26
ISBN (Electronic)9783662487976
ISBN (Print)9783662487969
DOIs
Publication statusPublished - 2015
Externally publishedYes
Event21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015 - Auckland, New Zealand
Duration: 29 Nov 20153 Dec 2015

Publication series

NameLecture Notes in Computer Science
PublisherSpringer Berlin Heidelberg
Volume9452
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

Other

Other21st International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2015
CountryNew Zealand
CityAuckland
Period29/11/153/12/15

Fingerprint Dive into the research topics of 'A provably secure group signature scheme from code-based assumptions'. Together they form a unique fingerprint.

Cite this