Paper 2018/779

Lattice-Based Group Signatures and Zero-Knowledge Proofs of Automorphism Stability

Rafael del Pino, Vadim Lyubashevsky, and Gregor Seiler

Abstract

We present a group signature scheme, based on the hardness of lattice problems, whose outputs are more than an order of magnitude smaller than the currently most efficient schemes in the literature. Since lattice-based schemes are also usually non-trivial to efficiently implement, we additionally provide the first experimental implementation of lattice-based group signatures demonstrating that our construction is indeed practical -- all operations take less than half a second on a standard laptop. A key component of our construction is a new zero-knowledge proof system for proving that a committed value belongs to a particular set of small size. The sets for which our proofs are applicable are exactly those that contain elements that remain stable under Galois automorphisms of the underlying cyclotomic number field of our lattice-based protocol. We believe that these proofs will find applications in other settings as well. The motivation of the new zero-knowledge proof in our construction is to allow the efficient use of the selectively-secure signature scheme (i.e. a signature scheme in which the adversary declares the forgery message before seeing the public key) of Agrawal et al. (Eurocrypt 2010) in constructions of lattice-based group signatures and other privacy protocols. For selectively-secure schemes to be meaningfully converted to standard signature schemes, it is crucial that the size of the message space is not too large. Using our zero-knowledge proofs, we can strategically pick small sets for which we can provide efficient zero-knowledge proofs of membership.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. Minor revision.CCS 2018
DOI
10.1145/3243734.3243852
Keywords
Group SignatureLatticesZero-KnowledgePost-QuantumImplementation
Contact author(s)
gseiler @ inf ethz ch
History
2018-09-01: received
Short URL
https://ia.cr/2018/779
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/779,
      author = {Rafael del Pino and Vadim Lyubashevsky and Gregor Seiler},
      title = {Lattice-Based Group Signatures and Zero-Knowledge Proofs of Automorphism Stability},
      howpublished = {Cryptology ePrint Archive, Paper 2018/779},
      year = {2018},
      doi = {10.1145/3243734.3243852},
      note = {\url{https://eprint.iacr.org/2018/779}},
      url = {https://eprint.iacr.org/2018/779}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.