Definition
A zero-knowledge proof must satisfy three properties:
- Completeness: if the statement is true, the honest verifier (that is, one following the protocol properly) will be convinced of this fact by an honest prover.
- Soundness: if the statement is false, no cheating prover can convince the honest verifier that it is true, except with some small probability.
- Zero-knowledge: if the statement is true, no cheating verifier learns anything other than this fact. This is formalized by showing that every cheating verifier has some simulator that, given only the statement to be proven (and no access to the prover), can produce a transcript that "looks like" an interaction between the honest prover and the cheating verifier.
The first two of these are properties of more general interactive proof systems. The third is what makes the proof zero-knowledge.
Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, they are probabilistic rather than deterministic. However, there are techniques to decrease the soundness error to negligibly small values.
A formal definition of zero-knowledge has to use some computational model, the most common one being that of a Turing machine. Let ,, and be turing machines. An interactive proof system with for a language is zero-knowledge if for any probabilistic polynomial time (PPT) verifier there exists an expected PPT simulator such that
The prover is modeled as having unlimited computation power (in practice, P usually is a Probabilistic Turing machine). Intuitively, the definition states that an interactive proof system is zero- knowledge if for any verifier there exists an efficient simulator that can reproduce the conversation between and on any given input. The auxiliary string in the definition plays the role of “prior knowledge”. The definition implies that cannot use any prior knowledge string to mine information out of its conversation with because we demand that if is also given this prior knowledge then it can reproduce the conversation between and just as before.
The definition given is that of perfect zero-knowledge. Computational zero-knowledge is obtained by requiring that the views of the verifier and the simulator are only computationally indistinguishable, given the auxiliary string.
Read more about this topic: Zero-knowledge Proof
Famous quotes containing the word definition:
“Beauty, like all other qualities presented to human experience, is relative; and the definition of it becomes unmeaning and useless in proportion to its abstractness. To define beauty not in the most abstract, but in the most concrete terms possible, not to find a universal formula for it, but the formula which expresses most adequately this or that special manifestation of it, is the aim of the true student of aesthetics.”
—Walter Pater (1839–1894)
“Although there is no universal agreement as to a definition of life, its biological manifestations are generally considered to be organization, metabolism, growth, irritability, adaptation, and reproduction.”
—The Columbia Encyclopedia, Fifth Edition, the first sentence of the article on “life” (based on wording in the First Edition, 1935)
“I’m beginning to think that the proper definition of “Man” is “an animal that writes letters.””
—Lewis Carroll [Charles Lutwidge Dodgson] (1832–1898)