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 1998] and proofs of knowledge [Feige, Fiat, and Shamir 1987; Tompa and Woll 1987].

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 16, 2009
Accession Number
AD1020564

Entities

People

  • Joseph Halpern
  • Rafael Pass
  • Vasumathi Raman

Organizations

  • Cornell University

Tags

Communities of Interest

  • Energy and Power Technologies

DTIC Thesaurus Topics

  • Algorithms
  • Automata
  • Computations
  • Computer Science
  • Decoding
  • Language
  • Machines
  • Notation
  • Numbers
  • Polynomials
  • Prime Numbers
  • Probability
  • Random Variables
  • Real Numbers
  • Security
  • Sequences
  • Simulators

Fields of Study

  • Computer science
  • Mathematics

Readers

  • Artificial Intelligence
  • Mathematical Modeling and Probability Theory.