sjb@cs.toronto.edu (Stephen Bellantoni) (08/28/89)
FLASH ANNOUNCEMENT
(SF = Sandford Fleming Building, 10 King's College Road)
-------------------------------------------------------------
THEORY SEMINAR
SF3203, at 3:00 p.m., Thursday 31 August 1989
Dr. Hugo Krawczyk
Technion - Haifa, Israel
"On the Composition of Zero-Knowledge Proof Systems"
A basic question concerning zero-knowledge proof systems is whether their
(sequential and/or parallel) composition is zero-knowledge too. This
question is not only of natural theoretical interest, but is also of great
practical importance as it concerns the use of zero-knowledge proofs as
subroutines in cryptographic protocols.
We prove that the original formulation of zero-knowledge as appearing in
the pioneering work of Goldwasser, Micali and Rackoff is not closed under
_s_e_q_u_e_n_t_i_a_l _c_o_m_p_o_s_i_t_i_o_n. This fact was conjuctered by many researchers
leading to the introduction of more robust formulations of zero-knowledge
(e.g. black-box simulation).
We prove that the general statement that the _p_a_r_a_l_l_e_l _c_o_m_p_o_s_i_t_i_o_n of any
two zero-knowledge protocols constitutes a zero-knowledge protocol, is
wrong. Namely, we present two protocols, both being zero-knowledge in a
strong sense yet their parallel composition is not zero-knowledge (not even
in a weak sense).
We present a lower bound on the round complexity of black-box simulation
zero-knowledge proofs of Arthur-Merlin type. We show that such proofs with
constant number of rounds exist only for languages in BPP. In particular,
this resolves an open problem concerning the "parallel versions" of the
original interactive proofs systems for quadratic residuosity, graph
isomorphism and any language in NP. It follows that these proof systems
are not black-box simulation zero-knowledge, unless the corresponding
languages are in BPP. The result concerning Arthur-Merlin zero-knowledge
proofs can be viewed as a support to the conjecture that "secret coins"
help in the zero-knowledge setting.
(_J_o_i_n_t _w_o_r_k _w_i_t_h _O_d_e_d _G_o_l_d_r_e_i_c_h.)