Monday, October 5 , 2009
4:00pm
5130 Upson Hall
Abstract:
Zero-knowledge protocols, introduced by Goldwasser, Micali and Rackoff in 1985, are fundamental cryptographic constructs. Whereas the classical zero-knowledge protocols only use *public-coins*, all known zero-knowledge protocols that remain secure under parallel composition rely on *private-coins*.
In 1990, Goldreich and Krawczyk showed that for *constant-round* black-box zero-knowledge protocols this phenomenon is inherent.
We show that this separation is inherent for all black-box zero-knowledge protocols, regardless of the round complexity. The core of our analysis is relies on a somewhat surprising connection between black-box zero-knowledge and hardness amplification techniques used in Raz' parallel repetition theorem for two-prover games.