Computer Science Colloquium, 2005-2006

Alon Rosen, Department of Electrical Engineering and Computer Science, Harvard University
December 28th, 2005

Zero-Knowledge and Cryptography in Complex Environments

The past three decades have witnessed a tremendous progress in the field of Cryptography. During these years, many cryptographic tasks have been put under rigorous treatment and numerous constructions realizing these tasks have been proposed. By now, the scope of cryptographic constructions ranges from simple schemes that realize ``atomic" tasks such as authentication, identification, and encryption, to fairly complex protocols that realize ``high-level" tasks such as secure multi-party computation.

The original setting in which cryptographic protocols were investigated consisted of one execution of the protocol at a time. While this served as a good starting point, it did not really provide a meaningful security guarantee in a large network scenario, where multiple executions of protocols are taking place concurrently. Such scenarios have become increasingly relevant in the late 90's, with the advent of large distributed networks (such as the Internet). This state of affairs has called for the re-establishment of the known feasibility results in settings that are closer to the "real world".

In this talk I will give an account of the progress made in the area of concurrent protocol execution (a.k.a. protocol composition). The talk will focus on the special case of zero-knowledge protocols, and on the pivotal role that they have played in the conceptualization and realization of more general (and "ambitious") cryptographic tasks.

Shuly Wintner
Last modified: Sun Dec 4 18:04:08 IST 2005