SPEAKER: Muthu Venkitasubramaniam TITLE: Private Coins versus Public Coins in Zero-Knowledge Proof Systems AUTHORS: Rafael Pass and Muthu Venkitasubramaniam ABSTRACT: 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. LINKS: http://www.cs.cornell.edu/%7Evmuthu/research/constZK.pdf