Proving one's identity is hard business. Part of that hardness comes from philosophical questions
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 life1…
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:
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!
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:
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?2
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 anything3 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
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:
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 (in the example ) can be given that gives the chances of successfully cheating during one round. The protocol is then repeated (possibly in an interleaved fashion) times to give the total cheating probability which can be tuned to perfection by choosing .
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 (efficiently5) 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.
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.
I am sorry to say that I made not only that mistake, but have also shown my face in public (potentially compromising face detection) and even touched things without properly bleaching everything immediately afterwards (potentially compromising DNA based systems). Since neither fingerprints nor DNA will probably change significantly soon, I can only hope that face detection prevails — and that I can find a good cosmetic surgeon… ↩
Assuming Victor chooses the bell to ring at random with equal probability, Peter has a 50% chance of guessing correctly each turn. Since only one failure to come out of the correct door will cause him to fail the test, he has to guess correctly each time to fool Victor. The chance to guess correctly times in a row is simply , giving a chance of only about one in a thousand for only ten repetitions. ↩
Yeah, yeah, the model example breaks down when Victor brings in CSI, or installs video surveillance not just in the garden, but also in his house, peeks during the first step, etc. pp. ↩
Note that in practice, the security of the ZKP also relies on how hard the secret can be found. If Victor where to bring in some kind of Ground Penetrating Radar
Most ZKP schemes require a way to create a commitment, i.e. a message that is both binding, meaning that the person that created the commitment cannot change what they committed to afterwards, and hidden, which means that nobody can divine the value that they committed to. This is usually done by assuming that some problem is so hard, as to be impossible in the real world. One possibility is to use a cryptographic hash function with a large per commitment salt; it is binding, as the issuer of the commitment would need to find multiple preimages mapping to the same value and hiding, as the attacker would have to guess the salt. An attacker with ridiculously magically double-infinite resources could nevertheless break both properties. ↩