A zero-knowledge proof is an interactive proof system in which a verifier's view can be simulated efficiently without interacting with the prover (Goldwasser et al. 1989, Goldreich et al. 1991, Numberphile2 2021). The simulation requirement applies to every efficient verifier, including one that departs from the prescribed protocol.
In the common-input formulation for a formal language 
, the prover and verifier receive the
same input 
.
The verifier's view consists of its input, random choices, and received messages.
For each verifier 
running in expected polynomial time, there must
exist a randomized algorithm 
running in expected polynomial
time that receives 
and produces a simulated view without access to the prover.
The real and simulated views must satisfy computational
indistinguishability as 
ranges over the valid inputs (Goldreich et al. 1991).
Perfect zero knowledge requires the two statistical distributions to be identical. Statistical zero knowledge requires their total
variation distance to be at most 
for every constant 
and all sufficiently long valid
inputs, where 
is the input length (Goldreich et al. 1991).
