Paper 2013/308

Lattice-Based Group Signatures with Logarithmic Signature Size

Fabien Laguillaumie, Adeline Langlois, Benoit Libert, and Damien Stehle


Group signatures are cryptographic primitives where users can anonymously sign messages in the name of a population they belong to. Gordon et al. (Asiacrypt 2010) suggested the first realization of group signatures based on lattice assumptions in the random oracle model. A significant drawback of their scheme is its linear signature size in the cardinality $N$ of the group. A recent extension proposed by Camenisch et al. (SCN 2012) suffers from the same overhead. In this paper, we describe the first lattice-based group signature schemes where the signature and public key sizes are essentially logarithmic in $N$ (for any fixed security level). Our basic construction only satisfies a relaxed definition of anonymity (just like the Gordon et al. system) but readily extends into a fully anonymous group signature (i.e., that resists adversaries equipped with a signature opening oracle). We prove the security of our schemes in the random oracle model under the SIS and LWE assumptions.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown status
group signatureslattice-based cryptography
Contact author(s)
damien stehle @ ens-lyon fr
2014-07-04: last of 2 revisions
2013-05-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Fabien Laguillaumie and Adeline Langlois and Benoit Libert and Damien Stehle},
      title = {Lattice-Based Group Signatures with Logarithmic Signature Size},
      howpublished = {Cryptology ePrint Archive, Paper 2013/308},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.