@conference {634703,
	title = {Composition of zero-knowledge proofs with efficient provers},
	booktitle = {Daniele Micciancio, editor, Proceedings of the 7th IACR Theory of Cryptography Conference (TCC {\textquoteleft}10), Lecture Notes on Computer Science},
	volume = {5978},
	year = {2010},
	pages = {572-587},
	publisher = {Springer-Verlag},
	organization = {Springer-Verlag},
	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{\textendash}Micali{\textendash}Rackoff (GMR) definition of zero knowledge (STOC {\textquoteleft}85), here called\&nbsp;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 Krawczyk (ICALP {\textquoteleft}90, SICOMP {\textquoteleft}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.

		
			\&nbsp;
		
	
	
		If we relax the GMR definition to only require that the simulation is indistinguishable from the verifier{\textquoteright}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.
		
			\&nbsp;
		
	
	
		We show that auxiliary-input zero knowledge with efficient provers is not closed under\&nbsp;parallel\&nbsp;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 {\textquoteleft}90) gave similar results under the seemingly incomparable assumptions that (a) the discrete logarithm problem is hard, or (b)\&nbsp;\(\mathcal{UP}\nsubseteq\mathcal{BPP}\)\&nbsp;and one-way functions exist.
	

},
	url = {https://link.springer.com/chapter/10.1007/978-3-642-11799-2_34},
	author = {Eleanor Birrell and Salil Vadhan}
}
