Zero Knowledge Proofs of Knowledge

Proving one's identity is hard business. Part of that hardness comes from philosophical questions  like "If I stop liking computers, does that future me constitute a different person?". In a way, some of these problems are repeated in the biometrics area, which have to distinguish between "real identities" and things that may look the same to their sensors , or even people that lose the things that provided their identity in accidents.

The most common method to deal with any of this is to rely on a Proof of Knowledge instead of a Proof of Identity, as this is not only easier to quantify, but also does not require special sensors and can be exchanged at will — after all if you accidentally left your fingerprints anywhere your biometric identity could be compromised for life¹…

The most basic variant of such a Proof of Knowledge is to simply have a shared secret, that you tell your communication partner to establish that you know it. While this is delightfully simple, it suffers from several problems:

1. If anyone can hear/see/etc you perform the proof, they can then impersonate your identity.
2. You need to use a different secret for every communication partner, or the same thing can happen. Are you using different passwords for every single logon you ever create?
3. It is a common misconception that passwords can be memorized by the average person. It is hard enough memorizing even a few actually secure passwords, doing so for every single logon is pretty much impossible, especially since you only need to logon to some services very rarely.
4. The secrecy of the shared secret also depends on the other communication partner. Are you sure that none  of  your  passwords  has  been  compromised  in  some  way ?

Pretty much all of these problems are due to one simple, basic truth: If you tell a secret to anybody, it is not a secret anymore!

Zero Knowledge Proofs of Knowledge

Most of those problems would simply go away if it were somehow possible to prove knowledge of a secret without giving away anything else. Surprisingly, such methods do exist, and are called Zero Knowledge Proof of Knowledge, or short Zero Knowledge Proof or ZKP, because they perform a proof of knowledge, but give away zero knowledge beyond that.

In spite of the very lofty terminology, ZKPs are really easy to understand. For example, Peter and Victor live next door to one another. One day Peter informs Victor that he knows of a secret door that connects both houses. Of course, Victor is skeptical and wants to see that door – but Peter wants to keep the secret.

To solve the dilemma, they meet up in front of the houses, where Victor has set up video surveillance of the gardens to prevent Peter from running around the back, and perform the following simple test:

1. Victor will close his eyes, and Peter will enter one of the houses through the front door.
2. Victor opens his eyes again, and rings one of the door bells.
3. Peter must now come out of the house where Victor rung the bell.

After performing the protocol, Victor, understandably, is still not convinced, as Peter may have simply gotten lucky. To convince Victor, Peter simply proposes to repeat the test a few times — after all, how often can one get lucky in a row?²

After performing the test for a few times, Victor starts to become convinced that Peter must be telling the truth. Thus, Peter proved his knowledge of a secret passage without giving away anything³ about the secret door beyond the fact that it must exist!

But wait, what if Peter really did just get lucky? After all, people do win the lottery ! To show the power of a protocol that can increase confidence by repetition, let us do two comparisons: Winning the Powerball (1 in 292 201 338 ) in a single try is more likely than successfully cheating 29 times. Guessing a random 12 character (printable) ASCII password (1 in 540 360 087 662 636 962 890 625) in a single try is more likely than successfully cheating 79 times. As you can see, depending on the expense for a single guess (hundreds of dollars for some lotteries down to almost nothing for a single password attempt against an encrypted file), it is easy to ensure that the ZKP is more secure than the other components⁴.

Σ-Protocols

In the previous example, Peter and Victor performed three steps in turn. Many more realistic ZKP schemes have a similar structure. These Σ-Protocols perform one round of the ZKP in the following way:

1. The prover (Peter) commits to something (which door he walks into)
2. The verifier (Victor) gives out a challenge (by ringing a door bell)
3. The prover (Peter) must now correctly respond to that challenge (by coming out of the right house)

Usually, the commitment and the response are mathematically connected in such a way that the prover either has to correctly divine the challenge or be in possession of the secret whose knowledge is to be proven. This way, a probability $0<p<1$ (in the example $p=0.5$) can be given that gives the chances of successfully cheating during one round. The protocol is then repeated (possibly in an interleaved fashion) $k$ times to give the total cheating probability $p^k$ which can be tuned to perfection by choosing $k$.

Simulators

While it seems intuitively clear that Victor cannot garner any knowledge from the protocol, we are still lacking a mathematical definition of what "zero knowledge" really means and how the property can be proven. The basic idea how to do so is very simple: If anyone can perform the protocol without knowing the secret, then they can gain nothing by observing someone else doing the protocol!

To implement this concept, we need the idea of a simulator, which is an algorithm that can be used to (efficiently) create a communication trace that cannot (efficiently⁵) be distinguished from a "real" communication trace. Giving such a simulator is possible since it plays both sides of the communication, and can thus predetermine what challenge will be given.

A simulator for the secret passage between Peter's and Victor's can be easily given: Simone can perform the protocol by simply deciding beforehand which door bell will be rung — and then simply committing to the right house. This way the cheating possibility is used to create a simulated communication that cannot be distinguished from a recorded transmission. It also shows quite well that such ZKPs need to be interactive; after all it is impossible to distinguish a recorded login by someone knowing the secret from a simulated one by someone not knowing it.

Summary

Proves of Knowledge are a cornerstone of the internet, where they are often used to prove identity. Common password authentication is one example that is particularly bad, as it requires the user to give the secret away to someone else — and a secret told is not a secret anymore.

It is possible to perform a so called Zero Knowledge Proof of Knowledge that proves the knowledge of a secret with arbitrary security. A common scheme to construct such protocols is that of Σ-Protocols, which consist of a commitment by the prover, followed by a challenge by the verifier and a response from the prover.

Mathematically the whole concept is supported by the idea of giving an efficient simulator algorithm that can generate something that looks identically to a recording of a successful Zero Knowledge Proof of Knowledge. The existence of a simulator not only proves the "Zero Knowledge" property, but also ensures that a recorded login attempt cannot be used afterwards to prove anything.

In the next post a ZKP is given that is built on a more interesting mathematical problem.