PKC'09: Invited Talks

Wednesday, March 18: Prof. Anna Lysyanskaya, Brown University:
From Signatures to Anonymous Credentials to Anonymous Delegation.

Abstract:

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. 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, pioneered by David Chaum, concerns itself with protocols that enable Alice to obtain and demonstrate possession of credentials without revealing unnecessary information. 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 and anonymous delegation.

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

Speaker's Short Bio:

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.

Thursday, March 19: Prof. Amit Sahai, UCLA:
A New Paradigm for Secure Protocols.

Abstract:

One of the most fundamental goals in cryptography is to design protocols that remain secure when adversarial participants can engage in arbitrary malicious behavior. In 1986, Goldreich, Micali, and Wigderson presented a powerful paradigm for designing such protocols: their approach reduced the task of designing secure protocols to designing protocols that only guarantee security against "honest-but-curious" participants. By making use of zero-knowledge proofs, the GMW paradigm enforces honest behavior without compromising secrecy. Over the past two decades, this approach has been the dominant paradigm for cryptographic protocol design. In this talk, we present a new general paradigm for secure protocol design. Our approach also reduces the task of designing secure protocols to designing protocols that only guarantee security against honest-but-curious participants. However, our approach avoids the use of zero-knowledge proofs, and instead makes use of multi-party protocols in a much simpler setting - where the majority of participants are completely honest (such multi-party protocols can exist without requiring any computational assumptions). Our paradigm yields protocols that rely on Oblivious Transfer (OT) as a building block. This offers a number of advantages in generality and efficiency. In contrast to the GMW paradigm, by avoiding the use of zero-knowledge proofs, our paradigm is able to treat all of its building blocks as "black boxes". This allows us to improve over previous results in the area of secure computation. In particular, we obtain:

  • Conceptually simpler and more efficient ways for basing unconditionally secure cryptography on OT.
  • More efficient protocols for generating a large number of OTs using a small number of OTs.
  • Secure and efficient protocols which only make a black-box use of cryptographic primitives or underlying algebraic structures in settings where no such protocols were known before.

This talk is based on joint works with Yuvali Ishai (Technion and UCLA) and Manoj Prabhakaran (UIUC).

Speaker's Short Bio:

Professor Amit Sahai received his Ph.D. in Computer Science from MIT in 2000. From 2000 to 2004, he was a professor at Princeton University; in 2004 he joined UCLA as an Associate Professor of Computer Science, and as Associate Director of the Center for Information and Computation Security. His research interests are in security and cryptography, and theoretical computer science more broadly. He has published more than 75 original technical research papers at venues such as the ACM Symposium on Theory of Computing (STOC), CRYPTO, and the Journal of the ACM. He has given a number of invited talks at institutions such as MIT, Stanford, and Berkeley, including the 2004 Distinguished Cryptographer Lecture Series at NTT Labs, Japan. Professor Sahai is the recipient of numerous honors; he was named an Alfred P. Sloan Foundation Research Fellow in 2002, and received an Okawa Research Award in 2007. His research has been covered by several news agencies including the BBC World Service.