zbMATH — the first resource for mathematics

Definitions and properties of zero-knowledge proof systems. (English) Zbl 0791.94010
Summary: We investigate some properties of zero-knowledge proofs, a notion introduced by O. Goldwasser, S. Micali, and C. Rackoff [Proc. 17th STOC, 291-304 (1985)]. We introduce and classify two definitions of zero-knowledge: auxiliary-input zero-knowledge and blackbox-simulation zero-knowledge. We explain why auxiliary-input zero- knowledge is a definition more suitable for cryptographic applications than the original definition. In particular we show that any protocol solely composed of subprotocols which are auxiliary-input zero-knowledge is itself auxiliary-input zero-knowledge. We show that blackbox- simulation zero-knowledge implies auxiliary-input zero-knowledge (which in turn implies the original definition). We argue that all known zero- knowledge proofs are in fact blackbox-simulation zero-knowledge (i.e., we proved zero-knowledge using blackbox-simulation of the verifier). As a result, all known zero-knowledge proof systems are shown to be auxiliary- input zero-knowledge and can be used for cryptographic applications such as those in [O. Goldreich, S. Micali, and A. Wigderson, How to play any mental game or a completeness theorem for protocols with honest majority, Proc. 19th STOC, pp. 218-229 (1987)].
We demonstrate the triviality of certain classes of zero-knowledge proof systems, in the sense that only languages in BPP have zero-knowledge proofs of these classes. In particular, we show that any language having a Las Vegas zero-knowledge proof system necessarily belongs to \(RP\). We show that randomness of both the verifier and the prover, and nontriviality of the interaction are essential properties of (nontrivial) auxiliary-input zero-knowledge proofs.

94A60 Cryptography
68P25 Data encryption (aspects in computer science)
68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
Full Text: DOI
[1] Aiello, W., and J. Hastad, Perfect Zero-Knowledge Languages Can Be Recognized in Two Rounds, Proc. 28th FOCS, 1987, pp. 439-448. · Zbl 0732.68038
[2] Aiello, W.; Hastad, J., Relativized Perfect Zero-Knowledge Is Not BPP, Inform. and Comput., Vol. 93, 223-240 (1992) · Zbl 0734.68043
[3] Babai, L., Trading Group Theory for Randomness, Proc. 17th STOC, 1985, pp. 421-429.
[4] Brassard, G.; Chaum, D.; Crepeau, C., Minimum Disclosure Proofs of Knowledge, J. Comput. System Sci., Vol. 37, No. 2, 156-189 (1988) · Zbl 0656.68109
[5] Feige, U., and A. Shamir, Personal communication.
[6] Fortnow, L., The Complexity of Perfect Zero-Knowledge, Proc. 19th STOC, 1987, pp. 204-209.
[7] Goldreich, O.; Goldwasser, S.; Micali, S., How To Construct Random Functions, J. Assoc. Comput. Mach., Vol. 33, No. 4, 792-807 (1986) · Zbl 0596.65002
[8] Goldreich, O.; Krawczyk, H., On the Composition of Zero-Knowledge Proof Systems, Proc. 17th ICALP, 268-282 (1990), Berlin: Springer-Verlag, Berlin · Zbl 0766.68033
[9] Goldreich, O., Y. Mansour, and M. Sipser, Interactive Proof Systems: Provers that Never Fail and Random Selection, Proc 28th FOCS, 1987, pp. 449-461.
[10] 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.
[11] Goldreich, O., S. Micali, and A. Wigderson, How to Play any Mental Game or a Completeness Theorem for Protocols with Honest Majority, Proc. 19th STOC, 1987, pp. 218-229.
[12] Goldwasser, S.; Micali, S., Probabilistic Encryption, J. Comput. System Sci., Vol. 28, No. 2, 270-299 (1984) · Zbl 0563.94013
[13] Goldwasser, S., S. Micali, and C. Rackoff, Knowledge Complexity of Interactive Proofs, Proc. 17th STOC, 1985, pp. 291-304. · Zbl 0900.94025
[14] Goldwasser, S.; Micali, S.; Rackoff, C., The Knowledge Complexity of Interactive Proof Systems, SIAM J. Comput., Vol. 18, No. 1, 186-208 (1989) · Zbl 0677.68062
[15] Goldwasser, S., and M. Sipser, Arthur Merlin Games Versus Interactive Proof Systems, Proc. 18th STOC, 1986, pp. 59-68.
[16] Impagliazzo, R.; Yung, M., Direct Minimum-Knowledge Computations, Advances in Cryptology—Crypto 87, 40-51 (1987), Berlin: Springer-Verlag, Berlin
[17] Oren, Y., Properties of Zero-Knowledge Proofs, M.Sc. Thesis, Computer Science Department, Technion, Haifa, Nov. 1987 (in Hebrew).
[18] Oren, Y., On the Cunning Power of Cheating Verifiers: Some Observations about Zero-Knowledge Proofs, Proc. 28th FOCS, 1987, pp. 462-471.
[19] A. Shamir, IP = PSPACE, Proc. 31st FOCS, 1990, pp. 11-15.
[20] Tompa, M., and H. Woll, Random Self-Reducibility and Zero-Knowledge Interactive Proofs of Possession of Information, Proc. 28th FOCS, 1987, pp. 472-482.
[21] Yao, A. C., Theory and Applications of Trapdoor Functions, Proc. 23rd FOCS, 1982, pp. 80-91.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.