International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Delegatable Anonymous Credentials

Authors:
Mira Belenkiy
Jan Camenisch
Melissa Chase
Markulf Kohlweiss
Anna Lysyanskaya
Hovav Shacham
Download:
URL: http://eprint.iacr.org/2008/428
Search ePrint
Search Google
Abstract: We construct an efficient delegatable anonymous credential system. Users can anonymously and unlinkably obtain credentials from any authority, delegate their credentials to other users, and prove possession of a credential $L$ levels away from the given authority. The size of the proof (and time to compute it) is $O(Lk)$, where $k$ is the security parameter. The only other construction of delegatable anonymous credentials (Chase and Lysyanskaya, Crypto 2006) relies on general non-interactive proofs for NP-complete languages of size $k \Omega(2^{L})$. We revise the entire approach to constructing anonymous credentials and identify \emph{randomizable} zero-knowledge proof of knowledge systems as the key building block. We formally define the notion of randomizable non-interactive zero-knowledge proofs, and give the first construction by showing how to appropriately rerandomize Groth and Sahai (Eurocrypt 2008) proofs. We show that such proof systems, in combination with an appropriate authentication scheme and a few other protocols, allow us to construct delegatable anonymous credentials. Finally, we instantiate these building blocks under appropriate assumptions about groups with bilinear maps.
BibTeX
@misc{eprint-2008-18105,
  title={Delegatable Anonymous Credentials},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / credentials anonymity NIZK},
  url={http://eprint.iacr.org/2008/428},
  note={ mchase@cs.brown.edu 14155 received 3 Oct 2008},
  author={Mira Belenkiy and Jan Camenisch and Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Hovav Shacham},
  year=2008
}