In *Proceedings
of Crypto
2009*,
vol. 5677 of
LNCS.
pages 108–125.
Springer-Verlag, Aug. 2009.

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Ω(2 ^{L})*.

We revise the entire approach to constructing anonymous
credentials and identify *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.

@InProceedings{BCCKLS09,
author = {Mira Belenkiy and Jan Camenisch and Melissa Chase
and Markulf Kohlweiss and Anna Lysyanskaya and Hovav
Shacham},
title = {Randomizable Proofs and Delegatable Anonymous
Credentials},
booktitle = {Proceedings of Crypto 2009},
editor = {Shai Halevi},
series = {LNCS},
year = 2009,
month = aug,
publisher = {Springer-Verlag},
volume = 5677,
pages = {108-25}
}