Composition of Zero-Knowledge Proofs with Efficient Provers
| Title: | Composition of Zero-Knowledge Proofs with Efficient Provers |
| Author: |
Birrell, Eleanor; Vadhan, Salil P.
Note: Order does not necessarily reflect citation order of authors. |
| Citation: | Birrell, Eleanor, and Salil Vadhan. 2010. Composition of zero-knowledge proofs with efficient provers. In Theory of Cryptography: 7th Theory of Cryptography Conference, TCC 2010, Zurich, Switzerland February 9-11, 2010 Proceedings. Lecture Notes on Computer Science 5978, ed. Daniele Micciancio. |
| Full Text & Related Files: |
vadhan_composition.pdf (207.4Kb; PDF) 
|
| 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: 1.) 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 Krawczyk (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. 2.) 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. 3.) 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 \nsubseteq BPP \) and one-way functions exist. |
| Published Version: | doi:10.1007/978-3-642-11799-2_34 |
| Other Sources: | http://eprint.iacr.org/2009/604.pdf |
| Terms of Use: | This article is made available under the terms and conditions applicable to Other Posted Material, as set forth at http://nrs.harvard.edu/urn-3:HUL.InstRepos:dash.current.terms-of-use#LAA |
| Citable link to this page: | http://nrs.harvard.edu/urn-3:HUL.InstRepos:4892999 |
This item appears in the following Collection(s)
-
FAS Scholarly Articles [5128]
Peer reviewed scholarly articles from the Faculty of Arts and Sciences of Harvard University
Contact administrator regarding this item (to report mistakes or request changes)
