Monday, October 20, 2014
12:00 PM
CSB 209
Muthu Venkitasubramaniam
University of Rochester
4-Round Resettably-Sound Zero-Knowledge
Zero-knowledge interactive proofs (ZK), introduced by Goldwasser, Micali and Rackoff [STOC 85] are paradoxical constructs that allow one player (called the Prover) to convince another player (called the Verifier) of the validity of a mathematical statement, while providing zero additional knowledge to the Verifier. Resettable-soundness introduced by Barak, Goldreich, Goldwasser and Lindell [FOCS' 01] is a strengthening of the soundness requirement in interactive proofs and additionally demands that even if a malicious prover is allowed to "reset" and "restart" the verifier it cannot convince the verifier of a false statement. This is relevant particularly when cryptographic protocols are implemented by devices that cannot reliably keep state (e.g., smart cards), and malicious entities can ``reset'' the device to a prior state easily. In the same work, they also provide the first construction of resettably-sound ZK proofs (rsZK) based on the breakthrough ``non-black-box'' simulation technique of Barak from [FOCS 01]. Most constructions of rsZK proofs rely on the existence of collision-resistant hash-functions. More recently, Chung, Pass and Seth [STOC 13] showed that rsZK can be based on the existence of one-way functions. This work resolves the minimal assumptions required to construct rsZK. However, less is known about the round-complexity of constructing such proofs. We essentially resolve this question and show how to construct 4-round rsZK from one-way functions. I will talk about some of the techniques involved in this construction and try to provide the necessary background.

Joint work with Kai-Min Chung, Rafail Ostrovsky, Rafael Pass, and Ivan Visconti.