# Composition of Zero-Knowledge Proofs

with Efficient Provers

Eleanor Birrell and Salil Vadhan

### Abstract

We revisit the composability of different forms of zero-knowledge proofs when the honest prover strategy is restricted to be polynomial time (given an appropriate auxiliary input). Our results are:

- When restricted to efficient provers, the original Goldwasser--Micali--Rackoff (GMR) definition of zero knowledge (STOC `85), here called
* plain zero knowledge,* is closed under a constant number of sequential compositions (on the same input). This contrasts with the case of unbounded provers, where Goldreich and Kraczyk (ICALP `90, SICOMP `96) exhibited a protocol that is zero knowledge under the GMR definition, but for which the sequential composition of 2 copies is not zero knowledge.

- If we relax the GMR definition to only require that the simulation is indistinguishable from the verifier's view by uniform polynomial-time distinguishers, with no auxiliary input beyond the statement being proven, then again zero knowledge is not closed under sequential composition of 2 copies.

- We show that auxiliary-input zero knowledge with efficient provers is not closed under
*parallel* composition of 2 copies under the assumption that there is a secure key agreement protocol (in which it is easy to recognize valid transcripts). Feige and Shamir (STOC `90) gave similar results under the seemingly incomparable assumptions that (a) the discrete logarithm problem is hard, or (b) UP\not\subseteq BPP and one-way functions exist.

### Versions

- Preliminary version, September 2009.[pdf]
- In
*Proceedings of the 7th IACR Theory of Cryptography Conference (TCC `10)*, volume 5978 of Lecture Notes on Computer Science, pages 572--587. Springer-Verlag, 9--11 February 2010. [Springer page][pdf]
*Cryptology ePrint Archive*, Report 2009/604, December 2009. [ePrint page][pdf]

[ back to
Salil Vadhan's research]