On the Composition of Public-coin Zero Knowledge


Wei-Lung (Dustin) Tseng


 Monday, October 5 , 2009

5130 Upson Hall



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.

Joint work with Rafael Pass and Douglas Wikstrom.