Muthu Venkitasubramaniam

Private Coins versus Public Coins in Zero-Knowledge Proof Systems

Rafael Pass and Muthu Venkitasubramaniam

Goldreich-Krawczyk (Siam J of Comp'96) showed that only
languages in BPP have constant-round public-coin black-box
zero-knowledge protocols. We extend their lower bound to ``fully
black-box'' private-coin protocols based on one-way functions. More
precisely, we show that only languages in BPP^Sam---where Sam is a
``collision-finding'' oracle in analogy with Simon (Eurocrypt'98) and
Haitner et. al (FOCS'07)---can have constant-round fully black-box
zero-knowledge proofs; the same holds for constant-round fully
black-box zero-knowledge arguments with sub-linear verifier
communication complexity. We also establish near-linear lower bounds
on the round complexity of fully black-box concurrent zero-knowledge
proofs (or arguments with sub-linear verifier communication) for
languages outside BPP^Sam.

The technique used to establish these results is a transformation from
private-coin protocols into Sam-relativized public-coin protocols; for
the case of fully black-box protocols based on one-way functions, this
transformation preserves zero knowledge, round complexity and
communication complexity.