Randomizable Proofs and Delegatable Anonymous Credentials

Mira Belenkiy, Jan Camenisch, Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Hovav Shacham

Research output: Chapter in Book/Report/Conference proceedingConference contribution


We construct an efficient delegatable anonymous credentials 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 a 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 Ω(2L ). 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 instance of controlled rerandomization of non-interactive zero-knowledge proofs by a third-party. Our construction uses Groth-Sahai proofs (Eurocrypt 2008).
Original languageEnglish
Title of host publicationAdvances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings
Number of pages18
ISBN (Electronic)978-3-642-03356-8
ISBN (Print)978-3-642-03355-1
Publication statusPublished - 2009
Event29th International Cryptology Conference - Santa Barbara, United States
Duration: 16 Aug 200920 Aug 2009


Conference29th International Cryptology Conference
Abbreviated titleCrypto 2009
Country/TerritoryUnited States
CitySanta Barbara
Internet address


Dive into the research topics of 'Randomizable Proofs and Delegatable Anonymous Credentials'. Together they form a unique fingerprint.

Cite this