(1) On the Composition of Public-Coin Zero-Knowledge Protocols

by Rafael Pass, Wei-Lung Dustin Tseng, and Douglas Wikstrum.

(2) On Public versus Private Coins in Zero-knowledge Proof Systems

by Rafael Pass and Muthuramakrishnan Venkitasubramaniam.

Oded's comments

Indeed, from my perspective, the common theme here is the justification of various features of known zero-knowledge protocols. Specifically, the first work [to appear in Crypto'09] explains why the only known protocols (i.e.,proofs or arguments) that preserve zero-knowledge under parallel composition are protocols that use private-coins. This paper shows that parallel executions of interactive arguments that are of the public-coin type cannot be simulated in a black-box manner (unless they are trivial; i.e., establish membership in a BPP-set). The second work [announced at the rump session of TCC'09] explains why the known construction of constant-round zero-knowledge proofs uses a (seemingly) stronger assumption than the mere existence of one-way functions. This paper provides an upper-bound on the computational complexity of sets having constant-round proof systems that use one-way functions in a "fully black-box" manner (i.e., the protocol makes a black-box use of the function, and the simulator uses the adversary in a black-box way).
Note that these justifications do not say that it is impossible to get rid of the aforementioned features of the known zero-knowledge protocols. They only says that doing so will require non-black-box techniques. Still this makes us feel better about our failure to get rid of these features so far (let alone in the past, before the potential of non-black-box techniques was realized).

The original abstract

Abstract for the 1st paper: We show that only languages in BPP have public-coin, black-box zero-knowledge protocols that are secure under an unbounded (polynomial) number of parallel repetitions. This results holds both in the plain model (without any set-up) and in the Bare Public-Key Model (where the prover and the verifier have registered public keys). We complement this result by showing the existence of a public-coin black-box zero-knowledge proof that remains secure under any a-priori bounded number of concurrent executions.
Abstract for the 2nd paper (tentative): Goldreich-Krawczyk show 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^CF$, where CF is a ``collision-finding'' oracle (as in [Haitner et al. 07], [Simon 98]), can have constant-round fully black-box zero-knowledge *proofs* based on one-way functions; the same holds for fully black-box zero-knowledge *arguments* with sublinear 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 sublinear verifier communication) for languages outside $BPP^CF$. To establish these results we present a transformation from private-coin protocols into CF-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. As an additional corollary of this transformation (and relying on recent parallel repetition theorems for public-coin protocols), we establish that parallel repetition reduces the soundness error in all fully black-box private-coin arguments with sublinear verifier communication complexity.

Back to list of Oded's choices.