From Signatures to Anonymous Credentials to Anonymous Delegation

Anna Lysyanskaya, Brown University

How does Alice convince Bob that she possesses a particular credential from Charlie? If Alice has a signature from Charlie on her public key, then all she will need to do is to show this signature to Bob, and also convince Bob that she is indeed Alice. In this setting, it is relatively clear how to revoke Alice’s credentials; also, one can limit the frequency and context of Alice’s credential use, and hold her accountable if she exceeds these limits.

How does Alice do this without revealing her identity to Bob, or indeed any identifying information? She produces a zero-knowledge proof of knowledge of the requisite values rather than showing them in the clear. Research on anonymous credentials concerns itself with protocols that enable Alice to obtain and demonstrate possession of credentials without revealing unnecessary information. It turns out that, similarly to the non-anonymous case, limits can be placed on the frequency and context of Alice’s use of anonymous credentials as well, and she can be identified and held accountable if she exceeds them.

Anonymous delegation is a research area that concerns itself with the next question: how does Alice delegate her credential to Bob without revealing any information about herself and learning anything about Bob?

In this talk, I will survey what we know so far about anonymous credentials, conditional anonymity and anonymous delegation. Specifically, I will outline generic constructions for these schemes, and give examples of specific instantiations. Some of these instantiations are efficient enough for practical use, have been implemented and piloted in real systems, and are part of a newly announced NIST-sponsored pilot on major U.S. university campuses in collaboration with Internet2.

This talk will be based on joint work with Mira Belenkiy, Jan Camenisch, Melissa Chase, Susan Hohenberger, Markulf Kohlweiss, Sarah Meiklejohn and Hovav Shacham.

Speaker Biography

Anna Lysyanskaya is an Associate Professor of Computer Science at Brown University. She received an A.B. in Computer Science and Mathematics from Smith College in 1997, and a Ph.D. in Computer Science and Electrical Engineering from MIT in 2002. She is a recipient of an NSF CAREER award and a Sloan Foundation fellowship and was included in the Technology Review Magazine’s list of 35 innovators under 35 for 2007. Her research interests are in cryptography, theoretical computer science, and computer security.