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 k {\Omega}(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 instance of controlled rerandomization of non-interactive zero-knowledge proofs by a third-party. Our construction uses Groth-Sahai proofs (Eurocrypt 2008).

}, author = {Mira Belenkiy and Jan Camenisch and Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Hovav Shacham}, booktitle = {CRYPTO 2009}, month = {August}, publisher = {Springer Verlag}, title = {Randomizable Proofs and Delegatable Anonymous Credentials}, url = {http://research.microsoft.com/apps/pubs/default.aspx?id=122759}, year = {2009}, }