(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.