research-article

An epistemic characterization of zero knowledge

Authors:

Joseph Y. Halpern,

Rafael Pass,

Vasumathi RamanAuthors Info & Claims

TARK '09: Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge

Pages 156 - 165

https://doi.org/10.1145/1562814.1562837

Published: 06 July 2009 Publication History

Get Access

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.

Google Scholar

[2]

Dwork, C., M. Naor, and A. Sahai (2004). Concurrent zero-knowledge. Journal of the ACM 51(6), 851--898.

Digital Library

Google Scholar

[3]

Fagin, R., J. Y. Halpern, Y. Moses, and M. Y. Vardi (1995). Reasoning About Knowledge. Cambridge, Mass.: MIT Press. A slightly revised paperback version was published in 2003.

Digital Library

Google Scholar

[4]

Feige, U., A. Fiat, and A. Shamir (1987). Zero knowledge proofs of identity. In Proc. 19th ACM Symposium on Theory of Computing, pp. 210--217.

Digital Library

Google Scholar

[5]

Feige, U. and A. Shamir (1990). Witness indistinguishability and witness hiding protocols. In Proc. 31st IEEE Symposium on Foundations of Computer Science, pp. 416--426.

Digital Library

Google Scholar

[6]

Goldreich, O. (2001). Foundations of Cryptography, Vol. 1. Cambridge University Press.

Digital Library

Google Scholar

[7]

Goldwasser, S., S. Micali, and C. Rackoff (1989). The knowledge complexity of interactive proof systems. SIAM Journal on Computing 18(1), 186--208.

Digital Library

Google Scholar

[8]

Halpern, J. Y., Y. Moses, and M. R. Tuttle (1988). A knowledge-based analysis of zero knowledge. In Proc. 20th ACM Symposium on Theory of Computing, pp. 132--147.

Digital Library

Google Scholar

[9]

Halpern, J. Y. and M. R. Tuttle (1993). Knowledge, probability, and adversaries. Journal of the ACM 40(4), 917--962.

Digital Library

Google Scholar

[10]

Moses, Y. (1988). Resource-bounded knowledge. In Proc. Second Conference on Theoretical Aspects of Reasoning about Knowledge, pp. 261--276.

Digital Library

Google Scholar

[11]

Rantala, V. (1982). Impossible worlds semantics and logical omniscience. Acta Philosophica Fennica 35, 18--24.

Google Scholar

[12]

Tompa, M. and H. Woll (1987). Random self-reducibility and zero knowledge interactive proofs of possession of information. In Proc. 28th IEEE Symposium on Foundations of Computer Science, pp. 472--482.

Digital Library

Google Scholar

Cited By

View all

Tang WBelle V(2024)ToM-LM: Delegating Theory of Mind Reasoning to External Symbolic Executors in Large Language ModelsNeural-Symbolic Learning and Reasoning10.1007/978-3-031-71170-1_20(245-257)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71170-1_20
Belle VFisher MRusso AKomendantskaya ENottle A(2024)Neuro-Symbolic AI + Agent Systems: A First Reflection on Trends, Opportunities and ChallengesAutonomous Agents and Multiagent Systems. Best and Visionary Papers10.1007/978-3-031-56255-6_10(180-200)Online publication date: 30-Mar-2024
https://doi.org/10.1007/978-3-031-56255-6_10
BELLE V(2023)Toward A Logical Theory Of Fairness and BiasTheory and Practice of Logic Programming10.1017/S1471068423000157(1-19)Online publication date: 19-Jul-2023
https://doi.org/10.1017/S1471068423000157
Show More Cited By

Index Terms

An epistemic characterization of zero knowledge
1. Computing methodologies
  1. Artificial intelligence
    1. Knowledge representation and reasoning
      1. Logic programming and answer set programming
  2. Modeling and simulation
    1. Model development and analysis
      1. Modeling methodologies
2. Theory of computation
  1. Logic
    1. Constraint and logic programming
  2. Models of computation
    1. Computability

Recommendations

On the Power of Statistical Zero Knowledge

We examine the power of statistical zero knowledge proofs (captured by the complexity class $\mathsf{SZK}$) and their variants. First, we give the strongest known relativized evidence that $\mathsf{SZK}$ contains hard problems, by exhibiting an oracle ...
On efficient zero-knowledge PCPs
TCC'12: Proceedings of the 9th international conference on Theory of Cryptography

We 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 ...
A knowledge-based analysis of zero knowledge
STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computing

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 ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

TARK '09: Proceedings of the 12th Conference on Theoretical Aspects of Rationality and Knowledge

July 2009

272 pages

ISBN:9781605585604

DOI:10.1145/1562814

Program Chair:
Aviad Heifetz
The Open University of Israel

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 06 July 2009

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Funding Sources

Conference

TARK '09

TARK '09: The 11th conference on Theoretical aspects of rationality and knowledge

July 6 - 8, 2009

California

Acceptance Rates

TARK '09 Paper Acceptance Rate 29 of 77 submissions, 38%;

Overall Acceptance Rate 61 of 177 submissions, 34%

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

5
Total Citations
View Citations
175
Total Downloads

Downloads (Last 12 months)4
Downloads (Last 6 weeks)0

Reflects downloads up to 20 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Tang WBelle V(2024)ToM-LM: Delegating Theory of Mind Reasoning to External Symbolic Executors in Large Language ModelsNeural-Symbolic Learning and Reasoning10.1007/978-3-031-71170-1_20(245-257)Online publication date: 9-Sep-2024
https://dl.acm.org/doi/10.1007/978-3-031-71170-1_20
Belle VFisher MRusso AKomendantskaya ENottle A(2024)Neuro-Symbolic AI + Agent Systems: A First Reflection on Trends, Opportunities and ChallengesAutonomous Agents and Multiagent Systems. Best and Visionary Papers10.1007/978-3-031-56255-6_10(180-200)Online publication date: 30-Mar-2024
https://doi.org/10.1007/978-3-031-56255-6_10
BELLE V(2023)Toward A Logical Theory Of Fairness and BiasTheory and Practice of Logic Programming10.1017/S1471068423000157(1-19)Online publication date: 19-Jul-2023
https://doi.org/10.1017/S1471068423000157
Belle V(2023)Excursions in First-Order Logic and Probability: Infinitely Many Random Variables, Continuous Distributions, Recursive Programs and BeyondLogics in Artificial Intelligence10.1007/978-3-031-43619-2_3(35-46)Online publication date: 24-Sep-2023
https://doi.org/10.1007/978-3-031-43619-2_3
Hansson S(2019)Technology and MathematicsPhilosophy & Technology10.1007/s13347-019-00348-9Online publication date: 26-Apr-2019
https://doi.org/10.1007/s13347-019-00348-9

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

On the Power of Statistical Zero Knowledge

On efficient zero-knowledge PCPs

A knowledge-based analysis of zero knowledge