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:
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)
“... if, as women, we accept a philosophy of history that asserts that women are by definition assimilated into the male universal, that we can understand our past through a male lens—if we are unaware that women even have a history—we live our lives similarly unanchored, drifting in response to a veering wind of myth and bias.”
—Adrienne Rich (b. 1929)
“Was man made stupid to see his own stupidity?
Is God by definition indifferent, beyond us all?
Is the eternal truth man’s fighting soul
Wherein the Beast ravens in its own avidity?”
—Richard Eberhart (b. 1904)