Zero-knowledge proof


Zero-knowledge proof (ZKP or zero-knowledge protocol) is a method by which the prover (Peggy) must prove to the verifier (Victor) that a given statement is true, without conveying any information apart from the fact that the statement is indeed true.[1]

Zero-knowledge proof, informally, is an interactive proof protocol that provides __highly convincing evidence__ that a statement is true or that Prover has certain knowledge (of a secret) and that Prover knows a (standard) proof of it while providing not a single bit of information about the proof (knowledge or secret). (In particular, Verifier who got convinced about the correctness of a statement cannot convince the third person about that.)

More formally A Zero-knowledge proof of a theorem T is an interactive two party protocol, in which Prover is able to convince Verifier who follows the same protocol, by the overwhelming statistical evidence, that T is true, if T is indeed true, but no Prover is not able to convince Verifier that T is true, if this is not so. In additions, during interactions, Prover does not reveal to Verifier any other information, except whether T is true or not. Consequently, whatever Verifier can do after he gets convinced, he can do just believing that T is true. Similar arguments hold for the case Prover possesses a secret.

If proving the statement requires knowledge of some secret information on the part of the prover, the definition implies that the verifier will not be able to prove the statement in turn to anyone else, since the verifier does not possess the secret information. Notice that the statement being proved must include the assertion that the prover has such knowledge (otherwise, the statement would not be proved in zero-knowledge, since at the end of the protocol the verifier would gain the additional information that the prover has knowledge of the required secret information). If the statement consists only of the fact that the prover possesses the secret information, it is a special case known as Zero-knowledge proof of knowledge, and it nicely illustrates the essence of the notion of Zero-knowledge proof: proving that one has knowledge of certain information is trivial if one is allowed to simply reveal that information; the challenge is proving that one has such knowledge without revealing the secret information or anything else.

For Zero-knowledge proofs of knowledge, the protocol must necessarily require interactive input from the verifier, usually in the form of a challenge or challenges such that the responses from the prover will convince the verifier if and only if the statement is true (i.e., if the prover does have the claimed knowledge). This is clearly the case, since otherwise the verifier could record the execution of the protocol and replay it to someone else: if this were accepted by the new party as proof that the replaying party knows the secret information, then the new party's acceptance is either justified – the replayer does know the secret information – which means that the protocol leaks knowledge and is not zero-knowledge, or it is spurious – i.e. leads to a party accepting someone's proof of knowledge who does not actually possess it.

Some forms of non-interactive Zero-knowledge proofs of knowledge exist, but the validity of the proof relies on computational assumptions (typically the assumptions of an ideal cryptographic Hash Function).

More Information#

There might be more information for this subject on one of the following: