An Introductory Survey to Zero-knowledge Proofs and their Applications

Friday, April 28, 2006 - 1:25pm - 3:00pm
Vincent 20
Giovanni Di Crescenzo (Telcordia)
The seemingly paradoxical notion of Zero-Knowledge Proof Systems, introduced by Goldwasser, Micali and Rackoff in the 80's, has received a great amount of attention in both the Cryptography and Computational Complexity literature. Very informally, a zero-knowledge proof is a method allowing a prover to convince a verifier of a statement without revealing any additional information other than the fact that the theorem is true. While the two requirements of 'convincing a verifier' and 'yet not revealing anything else' may seem hard to coexist, zero-knowledge proofs have found rigorous formulations and efficient instantiations in various settings. Furthermore, the general zero-knowledge methodology of revealing only the necessary minimal information in communication in the presence of adversaries has become a fundamental tool having wide applicability throughout Cryptography. In this talk we give an introductory survey to zero-knowledge proofs, their several variants and cryptographic applications.