Soundness (Interactive proof)
Encyclopedia
Soundness is a property of interactive proof system
s that requires that no prover can make the verifier accept for a wrong statement
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
, and every 
:
The above definition uses the somewhat arbitrary soundness error 2−80.
As long as the soundness error is bounded by a polynomial fraction of the potential running time of the verifier (i.e.
), it is always possible to amplify soundness until the soundness error becomes negligible relative to the running time of the verifier. This is achieved by repeating the proof and accepting only if all proofs verify. After 
repetitions, a soundness error 
will be reduced to 
.
Interactive proof system
In computational complexity theory, an interactive proof system is an abstract machine that models computation as the exchange of messages between two parties. The parties, the verifier and the prover, interact by exchanging messages in order to ascertain whether a given string belongs to a...
s that requires that no prover can make the verifier accept for a wrong statement
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
, and every :
The above definition uses the somewhat arbitrary soundness error 2−80.
As long as the soundness error is bounded by a polynomial fraction of the potential running time of the verifier (i.e.
), it is always possible to amplify soundness until the soundness error becomes negligible relative to the running time of the verifier. This is achieved by repeating the proof and accepting only if all proofs verify. After repetitions, a soundness error will be reduced to .