L. Fortnow
ABSTRACT
A Perfect Zero-Knowledge interactive proof system convinces a verifier that a string is in a language without revealing any additional knowledge in an information-theoretic sense. We show that for any language that has a perfect zero-knowledge proof system, its complement has a short interactive protocol. This result implies that there are not any perfect zero-knowledge protocols for NP-complete languages unless the polynomial time hierarchy collapses. This paper demonstrates that knowledge complexity can be used to show that a language is easy to prove.
- B.Babai, L., "Trading Group Theory for Randomness'', Proc. 17th STOC, 1985, pp. 421- 429. Google Scholar
Digital Library
- BH.Boppana, R. and J. Hastad, "Does co-NP Have Short Interactive Proofs?", IPL, to appear. Google ScholarDigital Library
- BC.Brassard, G. and C. Cr6peau, "Non- Transitive Transfer of Confidence' A Perfect Zero-Knowledge Interactive Protocol for SAT and Beyond", Pvoc. z97th FOCS, 1986, pp. 188-195.Google Scholar
- CW.Carter, J.L. and M.N. Wegman, "Universal Classes of Hash Functions", JC$$18 2, 1979, pp.143-154.Google Scholar
- GMW.Goldreich, O., S. Micali and A. Wigderson, "Proofs that Yield Nothing But their Validity and a Methodology of Cryptographic Protocol Design", Proc. 27th FOCS, 1986, pp. 174-187.Google ScholarDigital Library
- GMR.Goldwasser, S., S. Micali and C. Rackoff, "The Knowledge Complexity of Interactive Proof-Systems", Proc. 17th $TOC, 1985, pp. 291-304. Google ScholarDigital Library
- GS.Goldwasser, S. and M. Sipser, "Private Coins versus Public Coins in Interactive Proof Systems'', Proc. 18ih STOC, 1986, pp. 59-68. Google ScholarDigital Library
- S.Sipser, M., "A Complexity Theoretic Approach to Randomness", Proc. 15th STOC, 1983, pp. 330-335. Google ScholarDigital Library
Index Terms
- The complexity of perfect zero-knowledge
Recommendations
On efficient zero-knowledge PCPs
TCC'12: Proceedings of the 9th international conference on Theory of CryptographyWe revisit the question of Zero-Knowledge PCPs, studied by Kilian, Petrank, and Tardos (STOC '97). A ZK-PCP is defined similarly to a standard PCP, except that the view of any (possibly malicious) verifier can be efficiently simulated up to a small ...
Languages with efficient zero-knowledge PCPs are in SZK
TCC'13: Proceedings of the 10th theory of cryptography conference on Theory of CryptographyA Zero-Knowledge PCP (ZK-PCP) is a randomized PCP such that the view of any (perhaps cheating) efficient verifier can be efficiently simulated up to small statistical distance. Kilian, Petrank, and Tardos (STOC '97) constructed ZK-PCPs for all languages ...
Comments