An epistemic characterization of zero knowledge

ABSTRACT

Halpern, Moses and Tuttle presented a definition of interactive proofs using a notion they called practical knowledge, but left open the question of finding an epistemic formula that completely characterizes zero knowledge; that is, a formula that holds iff a proof is zero knowledge. We present such a formula, and show that it does characterize zero knowledge. Moreover, we show that variants of the formula characterize variants of zero knowledge such as concurrent zero knowledge [Dwork, Naor, and Sahai 2004] and proofs of knowledge [Feige, Fiat, and Shamir 1987; Tompa and Woll 1987].

REFERENCES

• 1: Bellare, M. and O. Goldreich (1992). A modular approach to the design and analysis of authentication and key exchange protocols. In Proc. CRYPTO '92, pp. 390--420.
• 2: Cynthia Dwork , Moni Naor , Amit Sahai, Concurrent zero-knowledge, Journal of the ACM (JACM), v.51 n.6, p.851-898, November 2004 [doi>10.1145/1039488.1039489]
• 3: Ronald Fagin , Joseph Y. Halpern , Moshe Y. Vardi , Yoram Moses, Reasoning about knowledge, MIT Press, Cambridge, MA, 1995
• 4: U. Fiege , A. Fiat , A. Shamir, Zero knowledge proofs of identity, Proceedings of the nineteenth annual ACM symposium on Theory of computing, p.210-217, January 1987, New York, New York, United States [doi>10.1145/28395.28419]
• 5: U. Feige , A. Shamir, Witness indistinguishable and witness hiding protocols, Proceedings of the twenty-second annual ACM symposium on Theory of computing, p.416-426, May 13-17, 1990, Baltimore, Maryland, United States [doi>10.1145/100216.100272]
• 6: Oded Goldreich, Foundations of Cryptography: Volume 1, Cambridge University Press, New York, NY, 2006
• 7: S. Goldwasser , S. Micali , C. Rackoff, The knowledge complexity of interactive proof systems, SIAM Journal on Computing, v.18 n.1, p.186-208, Feb. 1989 [doi>10.1137/0218012]
• 8: Joseph Halpern , Yjoram Moses , Mark Tuttle, A knowledge-based analysis of zero knowledge, Proceedings of the twentieth annual ACM symposium on Theory of computing, p.132-147, May 02-04, 1988, Chicago, Illinois, United States [doi>10.1145/62212.62224]
• 9: Joseph Y. Halpern , Mark R. Tuttle, Knowledge, probability, and adversaries, Journal of the ACM (JACM), v.40 n.4, p.917-960, Sept. 1993 [doi>10.1145/153724.153770]
• 10: Yoram Moses, Resource-bounded knowledge, Proceedings of the 2nd conference on Theoretical aspects of reasoning about knowledge, March 07-09, 1988, Pacific Grove, California
• 11: Rantala, V. (1982). Impossible worlds semantics and logical omniscience. Acta Philosophica Fennica 35, 18--24.
• 12: Martin Tompa , Heather Woll, Random self-reducibility and zero knowledge interactive proofs of possession of information, Proceedings of the 28th Annual Symposium on Foundations of Computer Science, p.472-482, October 12-14, 1987 [doi>10.1109/SFCS.1987.49]

INDEX TERMS

Primary Classification:
  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.4 Knowledge Representation Formalisms and Methods

Additional Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic

  I. Computing Methodologies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.3 Deduction and Theorem Proving
          Subjects: Logic programming
  I.6 SIMULATION AND MODELING
      I.6.5 Model Development
          Subjects: Modeling methodologies

General Terms:
Algorithms, Design, Theory