University of Tartu - ©2011 Rafik Chaabouni - Last update: 29.04.2014 11:09
Date: 11/03/2014 Location: J. Liivi 2, room 317 (next to the coffee room)
Speaker: Sven Laur & Rafik Chaabouni
Title: PoK, The Adversary Side
Abstract:
In this talk we review the basic way of how to convert challenge-response protocols into zero-knowledge proofs by using proofs of knowledge. First of all we introduce the simulation construction and study what properties of proof of knowledge determine the quality of simulation. In particular, we introduce the notion of simulation-failure and show that its profile determines the quality of simulation. Next we show how this profile can be computed for different types of proofs of knowledge. As a concrete result, we show that in order to achieve maximal simulation failure epsilon, the running time of knowledge extractor must be Omega(1/epsilon). Although this result is known to hold only for black-box reduction, it is widely believed that Omega(1/varepsilon) slowdown is unavoidable in the simulation construction. As a consequence, there are no known strict poly-time simulation algorithms for the zero-knowledge construction unless the proof of knowledge has variable number of rounds.
Additional Material:
http://epubs.siam.org/doi/abs/10.1137/S0097539703427975