An interactive proof system is a protocol in which a prover exchanges messages with a verifier to establish that an input belongs to a formal
language . The verifier is a randomized
algorithm running in polynomial time in the
input length. The prover has no restriction on computation
time (Goldwasser et al. 1989).
Let
be the probability that verifier
accepts input
after interacting with prover
, including the random choices of both participants.
In a standard constant-error formulation, completeness requires
for every . Soundness requires
for every
and every prover strategy
,
including computationally unrestricted strategies. Thus false assertions must be
rejected with high probability even when the prover
is dishonest. Sequential repetition with fresh randomness and majority acceptance
reduces the error (Goldwasser et al. 1989).
A zero-knowledge proof additionally requires an efficient simulation of the verifier's view.