Zero-knowledge proof

In cryptography, a zero-knowledge proof or zero-knowledge protocol is a method by which one party (the prover) can prove to another party (the verifier) that some given statement is true, while avoiding conveying to the verifier any information beyond the mere fact of that statement's truth.^[1] The intuition underlying zero-knowledge proofs is that it is trivial to prove possession of the relevant information simply by revealing it; the hard part is to prove this possession without revealing this information (or any aspect of it whatsoever).^[2]

In light of the fact that one should be able to generate a proof of some statement only when in possession of certain secret information connected to the statement, the verifier, even after having become convinced of the statement's truth, should nonetheless remain unable to prove the statement to further third parties.

In the plain model, nontrivial zero-knowledge proofs (i.e., those for languages outside of BPP) demand interaction between the prover and the verifier.^[3] This interaction usually entails the selection of one or more random challenges by the verifier; the random origin of these challenges, together with the prover's successful responses to them notwithstanding, jointly convince the verifier that the prover does possess the claimed knowledge. (If interaction were absent, then the verifier, having obtained the protocol's execution transcript—that is, the prover's one and only message—could replay that transcript to a third party, thereby convincing the third party that the verifier too possessed the secret information.)

In the common random string and random oracle models, non-interactive zero-knowledge proofs exist, in light of the Fiat–Shamir heuristic.^[4][5][6] These proofs, in practice, rely on computational assumptions (typically the collision-resistance of a cryptographic hash function).