eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2023/560

A Framework for Practical Anonymous Credentials from Lattices

Jonathan Bootle, IBM Research - Zurich
Vadim Lyubashevsky, IBM Research - Zurich
Ngoc Khanh Nguyen, École Polytechnique Fédérale de Lausanne
Alessandro Sorniotti, IBM Research - Zurich

We present a framework for building practical anonymous credential schemes based on the hardness of lattice problems. The running time of the prover and verifier is independent of the number of users and linear in the number of attributes. The scheme is also compact in practice, with the proofs being as small as a few dozen kilobytes for arbitrarily large (say up to $2^{128}$) users with each user having several attributes. The security of our scheme is based on a new family of lattice assumptions which roughly states that given short pre-images of random elements in some set $S$, it is hard to create a pre-image for a fresh element in such a set. We show that if the set admits efficient zero-knowledge proofs of knowledge of a commitment to a set element and its pre-image, then this yields practically-efficient privacy-preserving primitives such as blind signatures, anonymous credentials, and group signatures. We propose a candidate instantiation of a function from this family which allows for such proofs and thus yields practical lattice-based primitives.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in CRYPTO 2023
anonymous credentialslatticesblind signatures
Contact author(s)
jbt @ zurich ibm com
vad @ zurich ibm com
khanh nguyen @ epfl ch
aso @ zurich ibm com
2023-07-25: last of 2 revisions
2023-04-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jonathan Bootle and Vadim Lyubashevsky and Ngoc Khanh Nguyen and Alessandro Sorniotti},
      title = {A Framework for Practical Anonymous Credentials from Lattices},
      howpublished = {Cryptology ePrint Archive, Paper 2023/560},
      year = {2023},
      note = {\url{https://eprint.iacr.org/2023/560}},
      url = {https://eprint.iacr.org/2023/560}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.