In cryptography, a zero-knowledge proof, or zero-knowledge protocol (ZKP) is a method for one party to prove to another that a particular statement is true, without revealing anything other than the veracity of the statement in question.
A brief history of zero-knowledge proof systems
The notion of zero-knowledge systems was first introduced by Goldwasser, Micali, and Rackoff at the STOC’85 Annual ACM Conference on Theory of Computing in “The Knowledge Complexity of Interactive Proof Systems” (Goldwasser et al. 1989) where a group of mathematicians demonstrated how to prove to a verifier that a given integer is within a particular quadratic residue system. This was done without revealing information about the integer in question apart from its congruence to the quadratic residue system.
Their work has since been extended to work with other residue systems and can be used for the purpose of proving any NP-complete problem, or to demonstrate knowledge of a particular discrete logarithm. The latter may be used by a verifier in order to determine whether or not a given prover has knowledge of one of the prime factors of a particular semi-prime.
In “The Knowledge Complexity of Interactive Proof Systems” (Goldwasser et al. 1989) it was demonstrated that under a zero-knowledge proof system, a dishonest verifier.
This novel interactive proof system was the first to address the quandary of how an interactive proof system should behave in the presence of a dishonest or cheating verifier and demonstrated the property of being sound in the presence of both a dishonest prover, and a dishonest verifier.
It was also demonstrated that a cheating verifier does not learn anything about the secret associated with a given challenge-response round apart from the veracity of the proposition associated with the round in question. These protocols are also known as sigma protocols.
What does a zero-knowledge protocol actually do, though?
The following axioms for ZKPs were defined by Goldwasser et al. and must be satisfied by any interactive ZKP:
- Completeness: the verifier will always accept a given proof if the fact is true, as long as the both the prover, and the verifier abide by the protocol
- Soundness: the verifier will always reject a given proof if the fact is false, as long as the verifier follows the protocol; and
- Zero-knowledge: which states that the verifier learns nothing about the fact being proved, except that it is correct.
Simply put, an interactive zero-knowledge proof system is an interactive proof system which limits the exposure factor associated with the cryptographic material exchanged over-the-wire.
Rather than passing sensitive data between a prover, and a verifier in response to a particular challenge, a zero-knowledge protocol only ever tells the verifier small hints about the answer to a particular proposition.
It’s sort of like playing Guess Who except instead of asking your friend Joseph if his character has blue eyes, or a big, bushy mustache, you’re asking about infinitesimal details about his character’s appearance that don’t really tell you anything about what they look like on their own.
How did we get here, and where are we going?
Prior to Goldwasser et al., most of the work in the area of interactive proof systems focused chiefly on the soundness of a given proof system in the presence of a dishonest prover (Green, 2014). Such a prover may attempt to masquerade as a different party, or bend the rules of the protocol in order to learn more about a particular party.
Together with László Babai and Shlomo Moran, Goldwasser et al. were awarded the first Gödel Prize in theoretical computer science for their contributions to the field of interactive proof systems.
In “Proofs that yield nothing but their validity” (Oded Goldreich, et al. 1991) the NP-complete graph coloring problem was proven to be expressible as a ZKP proving that all problems in the class NP have an associated ZKP. This conclusion is valid because all problems in the complexity class NP are reducible to any other NP-complete problem.
This development was then swiftly built upon in “Everything Provable is Provable in Zero-knowledge” (Goldreich, Goldwasser et al) which demonstrated that any proposition which can be proven by an interactive proof system can be proved in zero knowledge assuming the existence of a secure probabilistic encryption scheme.
As a consequence, this proved that any problem verifiable in polynomial time by a deterministic Turing machine can be expressed as a ZKP.
A key take-away from this finding is that it means that any problem in the complexity class NP can be proven in zero-knowledge under the right circumstances, and that ZKPs have applications outside of identification, and authentication protocols.
The notion of witness indistinguishability was later introduced by Feige, Lapidot, and Shamir which improved the rigidity of the zero-knowledge property. This formative notion states a given pair of witnesses should be indistinguishable in the eyes of a given prover in order to allow for the sequential, parallel, and concurrent comparison of ZKPs without revealing extraneous information about the party associated with a given witness.
Challenge-response protocols (i.e. -protocols)
In order for a claimant to prove their knowledge of a given entity to a verifier an interactive challenge-response protocol may be employed:
- establish public ZKP parameters (i.e. a witness);
- : a challenge (i.e. a proposition);
- : a response (i.e. a proof of the proposition).
By iterating a particular challenge-response times the rigor of the protocol will be improved, and the margin of error associated with the proof will be reduced.
As a safeguard against dishonest verifiers the zero-knowledge property states that only the veracity of a given statement is revealed to a given verifier.
By employing an optional zero-knowledge property the verifier never learns the secret associated with a given user within the scope of a particular challenge-response protocol.
“Do you like Coke, or Pepsi?”
At its heart, a zero-knowledge proof is simply a probabilistic proof which is complete, sound, and exhibits the zero-knowledge property, but, what is a probabilistic proof?
Simply put, a probabilistic proof is a mathematical proof which can be used to convey the veracity of a given proposition with a small margin of error, and may be iterated over, and over again in order to improve its rigor as described previously.
As an example, a probabilistic interactive proof can be constructed which will let Bob (i.e. the verifier) know whether or not Alice (i.e. the prover) can taste the difference between Coke, and Pepsi by way of a blind taste test.
In this protocol, Alice turns her back, and asks Bob to pour a small amount of Coke into one cup, and Pepsi into another. Bob will then ask Alice if she can guess which brand of cola is in each cup.
If this protocol is iterated times then Bob can conclude with a probability of that Alice can really taste the difference between Coke, and Pepsi. Since Alice has the ability to convey to Bob whether she prefers Pepsi or Coke, the protocol is said to be complete. By iterating the protocol times a certain degree of soundness is achieved. However, the protocol does not protect either party against cheaters.
In order to protect against dishonest verifiers a ZKP can be constructed based on the aforementioned protocol by randomizing the contents of each cup at each iteration. In this version of the protocol, Pepsi or Coke may be in one cup, both cups, or neither. Since only Bob knows whether or not a given cup contains Pepsi, or Coke, the zero-knowledge property is said to be achieved.
Feige-Fiat-Shamir honest verifier ZKP
In the Feige-Fiat-Shamir identification protocol an arbiter first generates a random semi-prime modulus which is shared amongst all parties. The arbiter then assigns an asymmetric key pair for , where the public key is a quadratic residue (i.e. has a solution, and exists), and a private key .
In order for to prove her identity to , selects a random integer and sends to a verifier who in turn returns a random bit .
- If , sends to who asserts that , proving that knows ; or
- If , sends to who asserts that , proving that knows .
The bit, is used to denote the commitment scheme used within the protocol round. A bit commitment is used to partition a given protocol into two phases, namely a commit phase, and a reveal phase.
Loosely speaking, a commitment scheme is an efficient two-phase two-party protocol through which one party, called the sender can commit itself to a value so the following two conflicting requirements are satisfied:
- Secrecy: at the end of the commit phase, the other party, called the receiver does not gain any (computational) knowledge of the sender’s value. This requirement has to be satisfied even if the receiver tried to cheat; and
- Non-ambiguity: given the transcript of the interaction in the commit phase, there exists at most one value which the receiver may later (i.e. in the reveal phase) accept as a legal “opening” of the commitment. This requirement has to be satisfied even if the sender tries to cheat (O. Goldreich, and A. Kahan, 1996).
How to tell your friend that you know a particular discrete logarithm without giving everything up
As I mentioned earlier, a prover has the ability to demonstrate knowledge of a particular discrete logarithm without revealing the integer in question but, how does this actually work?
Let be a large prime, and let be a randomly chosen integer. Next, choose a generator , a secret integer compute , and publish .
In order for a prover to demonstrate to a verifier, that she has access to a private integer , the following -protocol may be used, where is a bit commitment:
- where ;
- Depending on the bit commitment scheme, :
- If ; or
- Depending on the bit commitment scheme, asserts:
- If computes (i.e that is a discrete log of );
- If computes which should equal
In the protocol the verifier only ever learns either or , but not in either branch of the commitment scheme.
A dishonest prover may attempt to cheat in one of two ways, namely in the first case by selecting a random which can be selected independent of , and then:
- Depending on the bit commitment scheme, :
- If fail, because you don’t know and you cannot easily compute an
- Given asserts that
A dishonest prover may also cheat by sending a discrete logarithm unrelated to such as for some random .
- where ;
- Depending on the bit commitment scheme, :
- If fail, because you don’t know , and you don’t know of an ; or
- Given asserts that
In either branch of the commitment scheme a dishonest verifier has a probability of being unearthed with a probability of . As a consequence, the probability of an honest verifier identifying the dishonest prover on a given round is when the protocol is iterated times (Canny, 2001).
So, zero-knowledge proofs are used everywhere, right?
Notwithstanding the advantageous zero-knowledge property of interactive ZKPs, the time complexity required to achieve a reasonable degree of soundness, and completeness hinders their effectiveness in practical applications.
Simply put, the time required to reduce the margin of error associated with probabilistic proofs makes these forms of interactive proof systems impractical in systems which are time-sensitive.
Furthermore, many ZKPs apart from password-authenticated key agreement (PAKE) protocols such as the Secure Remote Password protocol (SRP) require a one-time set-up which are often unsuitable for ephemeral connections.