Paper 2011/060

A Group Signature Scheme from Lattice Assumptions

S. Dov Gordon, Jonathan Katz, and Vinod Vaikuntanathan

Abstract

Group signature schemes allow users to sign messages on behalf of a group while (1) maintaining anonymity (within that group) with respect to an observer, yet (2) ensuring traceability of a signer (by the group manager) when needed. In this work we give the first construction of a group signature scheme based on lattices (more precisely, the learning with errors assumption), in the random oracle model. Toward our goal, we construct a new algorithm for sampling a random superlattice of a given modular lattice together with a short basis, that may be of independent interest.

Note: A preliminary version of this work was published in Asiacrypt 2010. This version is different in many ways -- the notation has been cleaned up to make the exposition more readable, we give a much better analysis of the parameters involved in the scheme, and we fixed a small mistake in the main construction of Setion 3.2.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Contact author(s)
gordon @ cs columbia edu
History
2011-02-08: revised
2011-02-07: received
See all versions
Short URL
https://ia.cr/2011/060
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/060,
      author = {S.  Dov Gordon and Jonathan Katz and Vinod Vaikuntanathan},
      title = {A Group Signature Scheme from Lattice Assumptions},
      howpublished = {Cryptology ePrint Archive, Paper 2011/060},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/060}},
      url = {https://eprint.iacr.org/2011/060}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.