A knowledge-based analysis of zero knowledge

ABSTRACT

While the intuition underlying a zero knowledge proof system [GMR85] is that no “knowledge” is leaked by the prover to the verifier, researchers are just beginning to analyze such proof systems in terms of formal notions of knowledge. In this paper, we show how interactive proof systems motivate a new notion of practical knowledge, and we capture the definition of an interactive proof system in terms of practical knowledge. Using this notion of knowledge, we formally capture and prove the intuition that the prover does not leak any knowledge of any fact (other than the fact being proven) during a zero knowledge proof. We extend this result to show that the prover does not leak any knowledge of how to compute any information (such as the factorization of a number) during a zero knowledge proof. Finally, we define the notion of a weak interactive proof in which the prover is limited to probabilistic, polynomial-time computations, and we prove analogous security results for such proof systems. We show that, in a precise sense, any nontrivial weak interactive proof must be a proof about the prover's knowledge, and show that, under natural conditions, the notions of interactive proofs of knowledge defined in [TW87] and [FFS87] are instances of weak interactive proofs.

REFERENCES

• BC86: G. Brassard and C. Crepeau, Nontransitive transfer of confidence: A perfect zero-knowledge interactive protocol for SAT and beyond, Pear. 27th IEEE Syrup. on Foundations of Computer Science, 1986, pp. 188-195.
• CM86: K. M. Chandy , Jayadev Misra, How processes learn, Distributed Computing, v.1 n.1, p.40-52, Jan. 1986 [doi>10.1007/BF01843569]
• DM86: C Dwork , Y Moses, Knowledge and common knowledge in a Byzantine environment I: crash failures, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.149-169, March 1986, Monterey, California, United States
• DS88: C. Dwork and L. Stockmeyer, Interactive proof systems with finite state verifiers (extended abstract), 1988. Unpublished manuscript.
• FFS87: U. Fiege , A. Fiat , A. Shamir, Zero knowledge proofs of identity, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.210-217, January 1987, New York, New York, United States [doi>10.1145/28395.28419]
• FH88: Ronald Fagin , Joseph Y. Halpern, Reasoning about Knowledge and Probability, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.277-293, March 01, 1988
• FI86: M Fischer , N Immerman, Foundations of knowledge for distributed systems, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.171-185, March 1986, Monterey, California, United States
• For87: L. Fortnow, The complexity of perfect zero-knowledge, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.204-209, January 1987, New York, New York, United States [doi>10.1145/28395.28418]
• FZ87: M.J. Fischer and I,. D. Zlick, Relative Knowledge and Belief ('Ev, ten ded Abstract), 'Focl~l~ical Report YALEII/DCS/FFIt-589, Yale Uiliversi~y, Decend)er 1987.
• FZ88: M.J. Fischer and L. D. Zuck, Uncertain Knowledge in Distributed Systems, Technical Report YALEU/DCS/TR-604, Yale U~iversity, January 1988.
• GHY85: A. GMil, S. itaber, and M. Yung, A private interactive test of a boolean predicate and minimuln-knowledge public-key cryptosysterns, Proc. 26th {EEE Syrup. on Founda. lions of Computer Science, 1985, pp. 360- 371.
• GMR85: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• GMW86: O. Goldreich, S. Micali, and A. Wigderson, Proofs that yield nothing but tlteir validity and a methodology of crypotgraphic design, Pvoc. 27th IEEE Syrup. on Foundations of Computer Science, 1986.
• GS87: S Goldwasser , M Sipser, Private coins versus public coins in interactive proof systems, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.59-68, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12137]
• Had87: V. Hadzilacos, A knowledge-theoretic analysis of atomic commitment protocols, Proceedings of the sixth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.129-134, March 23-25, 1987, San Diego, California, United States [doi>10.1145/28659.28672]
• Hal87: j. Y. Halpern, Using reasoning about knowledge to analyze distributed systems, Annual Review of Computer Science, Vol. ~2, Allnllal Reviews Inc., 1987, pp. 37-68.
• HF85: Joseph Y. Halpern , Ronald Fagin, A formal model of knowledge, action, and communication in distributed systems: preliminary report, Proceedings of the fourth annual ACM symposium on Principles of distributed computing, p.224-236, August 1985, Minaki, Ontario, Canada [doi>10.1145/323596.323617]
• HM84: Joseph Y. Halpern , Yoram Moses, Knowledge and common knowledge in a distributed environment, Proceedings of the third annual ACM symposium on Principles of distributed computing, p.50-61, August 27-29, 1984, Vancouver, British Columbia, Canada [doi>10.1145/800222.806735]
• HZ87: Joseph Y. Halpern, A little knowledge goes a long way: simple knowledge-based derivations and correctness proofs for a family of protocols, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.269-280, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41863]
• LR86: R Ladner , J Reif, The logic of distributed protocols, Proceedings of the 1986 Conference on Theoretical aspects of reasoning about knowledge, p.207-222, March 1986, Monterey, California, United States
• MDH86: Y. Moses, D. Dolce, and J. Y. Halpern, Cheating husbands and other stories: a case study of knowledge, action, and communication, Distributed Computing 1:3, 1986, pp. 167-176.
• Moo85: R.C. Moore, A formal theory of knowledge and action, Formal Theories of the Commonsense World (J. llobbs and R. C. Moore, eds.), Ablex Publishing Corp., 1985.
• Mos88: Yoram Moses, Resource-bounded Knowledge, Proceedings of the 2nd Conference on Theoretical Aspects of Reasoning about Knowledge, p.261-275, March 01, 1988
• MT88: Y. Moses and M. Tuttle, Programming simultaneous actions using common knowledge, Algorithmica 3, 1988, pp. I21-169. A preliminary version appeared in Proc. 27th IEEE Symp. on Foundations of Computer Science, 1986.
• NT87: Gil Neiger , Sam Toueg, Substituting for real time and common knowledge in asynchronous distributed systems, Proceedings of the sixth annual ACM Symposium on Principles of distributed computing, p.281-293, August 10-12, 1987, Vancouver, British Columbia, Canada [doi>10.1145/41840.41864]
• Ore87: Y. Oren, On the cunning power of cheating verifiers: some observations about zero knowledge proofs, Proc. ~8th IEEE Syrup. on Foundations of Computer Science, 1987, pp. 462-471.
• PR85: Rohit Parikh , R. Ramanujam, Distributed Processes and the Logic of Knowledge, Proceedings of the Conference on Logic of Programs, p.256-268, June 17-19, 1985
• TW87: M. Tompa and H. Woll, Random selfreducibility and zero knowledge interactive proofs of possession of information, Proc. 28th IEEE $ymp. on Foundations of Computer Science, 1987.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Proof theory

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

General Terms:
Algorithms, Design, Performance, Theory