Editing Interactive proof system (section)

== Background ==

Every interactive proof system defines a [[formal language]] of strings <math>L</math>. '''Soundness''' of the proof system refers to the property that no prover can make the verifier accept for the wrong statement <math>y \not\in L</math> except with some small probability. The upper bound of this probability is referred to as the '''soundness error''' of a proof system. More formally, for every prover <math>(\tilde{\mathcal{P}})</math>, and every <math>y \not\in L</math>:

: <math>\Pr[(\perp,(\text{accept}))\gets (\tilde{\mathcal{P}})(y) \leftrightarrow (\mathcal{V})(y)] < \epsilon.</math>

for some <math> \epsilon \ll 1 </math>.
As long as the soundness error is bounded by a polynomial fraction of the potential running time of the verifier (i.e. <math>\epsilon\leq1/\mathrm{poly}(|y|)</math>), it is always possible to amplify soundness until the soundness error becomes [[negligible function]] relative to the running time of the verifier. This is achieved by repeating the proof and accepting only if all proofs verify. After <math>\ell</math> repetitions, a soundness error <math>\epsilon</math> will be reduced to <math>\epsilon^\ell</math>.<ref>{{citation|first=Oded|last=Goldreich|authorlink=Oded Goldreich|title=Zero-Knowledge twenty years after its invention|year=2002|id={{ECCC|2002|02|063}}}}.</ref>