Zero-knowledge proof
- Snippet from Wikipedia: 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 a given statement is true, while avoiding conveying to the verifier any information beyond the mere fact of the statement's truth. The intuition underlying zero-knowledge proofs is that it is trivial to prove the possession of certain information by simply revealing it; the challenge is to prove this possession without revealing the information, or any aspect of it whatsoever.
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 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. 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 weren't present, 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. These proofs, in practice, rely on computational assumptions (typically the collision-resistance of a cryptographic hash function).