Editing Zero-knowledge proof (section)

== Definition ==
{{more citations needed|section|date=July 2022}}
A zero-knowledge proof of some statement must satisfy three properties:

# '''Completeness''': if the statement is true, then an 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, then no cheating prover can convince an honest verifier that it is true, except with some small probability.
# '''Zero-knowledge''': if the statement is true, then no verifier learns anything other than the fact that the statement is true. In other words, just knowing the statement (not the secret) is sufficient to imagine a scenario showing that the prover knows the secret. This is formalized by showing that every verifier has some ''simulator'' that, given only the statement to be proved (and no access to the prover), can produce a transcript that "looks like" an interaction between an honest prover and the verifier in question.

The first two of these are properties of more general [[interactive proof system]]s. The third is what makes the proof zero-knowledge.<ref>{{Cite journal |last1=Feige |first1=Uriel |last2=Fiat |first2=Amos |last3=Shamir |first3=Adi |date=1988-06-01 |title=Zero-knowledge proofs of identity |journal=Journal of Cryptology |language=en |volume=1 |issue=2 |pages=77–94 |doi=10.1007/BF02351717 |s2cid=2950602 |issn=1432-1378|doi-access=free }}</ref>

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, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values (for example, guessing correctly on a hundred or thousand binary decisions has a 1/2<sup>100</sup> or 1/2<sup>1000</sup> soundness error, respectively. As the number of bits increases, the soundness error decreases toward zero).

A formal definition of zero-knowledge must use some computational model, the most common one being that of a [[Turing machine]]. Let {{Mvar|P}}, {{Mvar|V}}, and {{Mvar|S}} be Turing machines. An [[interactive proof system]] with {{Mvar|(''P'',''V'')}} for a language {{Mvar|L}} is zero-knowledge if for any [[probabilistic polynomial time]] (PPT) verifier <math>\hat V</math> there exists a PPT simulator {{Mvar|S}} such that:

: <math>\forall x \in L, z \in \{0, 1\}^{*}, \operatorname{View}_{\hat V} \left[P(x) \leftrightarrow \hat V(x, z)\right] = S(x, z),</math>

where {{Math|View<sub>''<math>\hat V</math>''</sub>[''P''(''x'')&harr;''<math>\hat V</math>''(''x'',''z'')]}} is a record of the interactions between {{Math|''P''(''x'')}} and {{Math|''V''(''x'',''z'')}}. The prover {{Mvar|P}} is modeled as having unlimited computation power (in practice, {{Mvar|P}} usually is a [[probabilistic Turing machine]]). Intuitively, the definition states that an interactive proof system {{Math|(''P'',''V'')}} is zero-knowledge if for any verifier <math>\hat V</math> there exists an efficient simulator {{Mvar|S}} (depending on <math>\hat V</math>) that can reproduce the conversation between {{Mvar|P}} and <math>\hat V</math> on any given input. The auxiliary string {{Mvar|z}} in the definition plays the role of "prior knowledge" (including the random coins of <math>\hat V</math>). The definition implies that <math>\hat V</math> cannot use any prior knowledge string {{Mvar|z}} to mine information out of its conversation with {{Mvar|P}}, because if {{Mvar|S}} is also given this prior knowledge then it can reproduce the conversation between <math>\hat V</math> and {{Mvar|P}} just as before. {{citation needed|date=June 2021}}

The definition given is that of perfect zero-knowledge. Computational zero-knowledge is obtained by requiring that the views of the verifier <math>\hat V</math> and the simulator are only [[computational indistinguishability|computationally indistinguishable]], given the auxiliary string. {{citation needed|date=June 2021}}