International Association for Cryptologic Research

International Association
for Cryptologic Research


A Framework for Practical Anonymous Credentials from Lattices

Vadim Lyubashevsky , IBM Research Europe
Ngoc Khanh Nguyen , EPFL
Jonathan Bootle , IBM Research Europe
Alessandro Sorniotti , IBM Research Europe
DOI: 10.1007/978-3-031-38545-2_13 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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.
  title={A Framework for Practical Anonymous Credentials from Lattices},
  author={Vadim Lyubashevsky and Ngoc Khanh Nguyen and Jonathan Bootle and Alessandro Sorniotti},