The Knowledge Complexity of Interactive Proof Systems

By Shafi Goldwasser, Silvio Micali, C. Rackoff. 1989

Usually, a proof of a theorem contains more knowledge than the mere fact that the theorem is true. For instance, to prove that a graph is Hamiltonian it suffices to exhibit a Hamiltonian tour in it; however, this seems to contain more knowledge than the single bit Hamiltonian/non-Hamiltonian.In this paper a computational complexity theory of the “knowledge” contained in a proof is developed. Zero-knowledge proofs are defined as those proofs that convey no additional knowledge other than the correctness of the proposition in question. Examples of zero-knowledge proof systems are given for the languages of quadratic residuosity and 'quadratic nonresiduosity. These are the first examples of zero-knowledge proofs for languages not known to be efficiently recognizable.

Subfields: Privacy & Security, Algorithms & Complexity

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Privacy & Security

In Algorithms & Complexity

Citations in the corpus

Advances and Open Problems in Federated Learning (2019, background): “t depend on secret information known to the prover, called witness, without revealing those secrets to the veriﬁer. The notion of zero-knowledge was introduced in the late 1980’s by Goldwasser et al. [184]. It provides a solution for the veriﬁability question on private data. While there had been a ”
Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “These three security properties are nearly identical to the properties required of a zero-knowledge interactive proof system [70].”
Geppetto: Versatile Verifiable Computation (2015, background): “Prior work on verifying computation focused on narrow classes of computation [32, 51], relied on physical-security assumptions [41, 47], assumed uncorrelated failures [19, 20], or achieved good asymptotics [2, 28, 30, 31, 33, 38, 44] but impractical concrete performance [46, 50].”
Pinocchio: Nearly Practical Verifiable Computation (2013, background): “Finally, the theory community has produced a number of beautiful, general-purpose protocols [16–23] that offer compelling asymptotics.”
Gazelle: A Low Latency Framework for Secure Neural Network Inference (2018, background): “We ask for the cryptographic standard of ideal/real security [17], [18].”
Verifying computations with state (2013, methodology): “The client could use a tailored solution [8, 13, 18, 28, 39, 58, 70, 73, 75], but such solutions are not available for all applications.”
Spartan: Efficient and general-purpose zkSNARKs without trusted setup (2020, background): “The early works on interactive proofs [10, 61] focus on studying the power of IPs in the context of intractable languages.”
Private memoirs of a smart meter (2010, background): “Zero-Knowledge (ZK) protocols [10] are challenge-response protocols that allow the prover to demonstrate the knowledge of a secret to the verifier, without revealing any partial information that would help the verifier infer the secret, other than the fact that the prover knows the secret.”
On the existence of extractable one-way functions (2014, methodology): “We then use these functions to construct the first 2-message zero-knowledge arguments and 3-message zeroknowledge arguments of knowledge, against the same class of adversarial verifiers, from essentially the same assumptions.”
Provably Secure Higher-Order Masking of AES (2010, result): “As in [18], our proofs shall apply similar techniques as zero-knowledge proofs [16].”