Paper 2018/034

Constant-size Group Signatures from Lattices

San Ling, Khoa Nguyen, Huaxiong Wang, and Yanhong Xu

Abstract

Lattice-based group signature is an active research topic in recent years. Since the pioneering work by Gordon, Katz and Vaikuntanathan (Asiacrypt 2010), ten other schemes have been proposed, providing various improvements in terms of security, efficiency and functionality. However, in all known constructions, one has to fix the number $N$ of group users in the setup stage, and as a consequence, the signature sizes are dependent on $N$. In this work, we introduce the first constant-size group signature from lattices, which means that the size of signatures produced by the scheme is independent of $N$ and only depends on the security parameter $\lambda$. More precisely, in our scheme, the sizes of signatures, public key and users' secret keys are all of order $\widetilde{\mathcal{O}}(\lambda)$. The scheme supports dynamic enrollment of users and is proven secure in the random oracle model under the Ring Short Integer Solution (RSIS) and Ring Learning With Errors (RLWE) assumptions. At the heart of our design is a zero-knowledge argument of knowledge of a valid message-signature pair for the Ducas-Micciancio signature scheme (Crypto 2014), that may be of independent interest.

Metadata
Available format(s)
PDF
Publication info
A minor revision of an IACR publication in PKC 2018
Keywords
lattice-based cryptographyconstant-size group signatureszero-knowledge proofsDucas-Micciancio signature
Contact author(s)
xu0014ng @ ntu edu sg
History
2018-01-08: received
Short URL
https://ia.cr/2018/034
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/034,
      author = {San Ling and Khoa Nguyen and Huaxiong Wang and Yanhong Xu},
      title = {Constant-size Group Signatures from Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2018/034},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/034}},
      url = {https://eprint.iacr.org/2018/034}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.