Proving without knowing: Zero-knowledge proof
Alice has two boxes of same size and shape(identical), except one box is red and the other box is blue. Bob’s needs to verify that Alice has two boxes that have different colors. But, Alice does not like to reveal the colors of the boxes. How does Alice suppose to prove that two boxes have different colors without revealing the colors of the boxes?
Here, Alice called as “prover” since she needs to prove her statement. Bob called “Verifier” since he needs to verify that Alice statement is correct or not. Can you imagine how Alice and Bob find the way to prove Alice statement? Ok. Here is the answer. Alice blindfold the Bob such that he cannot see the color of the box. Now, Bob takes each of the boxes which are physically identical to each hand and show it to Alice. Assume, Bob took the red box to the right arm and blue box to the left arm. Now, Bob secretly swaps the boxes in his hand without showing to Alice. Now blue box in Bob’s right hand and red box in left hand. Bob ask Alice “Does boxes are swapped or not?”. If two boxes have a different color, then Alice can tell that boxes are swapped. If two boxes are exactly identical, then Alice unable to tell whether boxes are swapped or not. Which means, Alice answer has 50% of chance to be correct or not if two boxes are identical.
Next time Bob don’t swap the boxes and ask Alice that “Does boxes are swapped or not?” If Alice says no, then Alice statement is wrong. If Alice says yes, then it may or may not true. Bob can iterate this process multiple time until he confident that Alice statement was true. In this method, Bob does not have any idea about the box color.
Here the probability tree for the above scenario
The first iteration, Bob can say 50% probability that Alice statement is not false. If Alice answer correctly in second time, Bob can say Alice statement was not false by 75 %. In the third iteration, it would be 87.5%. Bob can continue the process until he satisfies with the result.
Zero-Knowledge proof must satisfy the following conditions
- Completeness: If the original statement is true and follow the correct protocol, then verifier naturally becomes convince.
- Soundness: If the original statement is false, verifier found mismatches in provers feedback
- Zero knowledge: If the statement is true, verifier does not learn anything other than the statement is true.
In this example If Alice’s statement was correct, then Alice answers each of the time correctly. This is called Completeness. If two boxes are identical, then Alice unable to tell whether Bob swap or didn't swap the box. This is called Soundness. In this protocol Bob unable to see the color of the boxes. This is called Zero knowledge.
Ali Baba’s Cave Problem
Ali Baba's cave problem is a most popular question in zero-knowledge proof and its published in “How to Explain Zero-Knowledge Protocols to Your Children” paper. Here the question simply. There is a cave which has two entries inside called A and B. Both entries are connected inside the cave by a door that can open if correct secret spell words known. Peggy says Victors that she knows the secret spell to open the door. Further, Peggy also does not like to reveal which path she entered. How Peggy supposed to prove that she knows the secret spell without telling Victor the spell and without telling from which entrance she entered.
Here the steps to prove or disprove that Peggy knows the secret spell to open the door in the cave.
Peggy enters the cave and takes a random path while Victor keeps outside the cave. Once Peggy takes the path Victor comes inside the cave and shout Peggy to come out in path A. If Peggy already entered in path A, she can come outside from the path A even she does not know the secret spell. But, If she entered the cave in path B, then she needs to know the secret spell to come outside in path A.
Proving Age Without Revealing Age
Here, another interesting problem. Alice needs to enter into a club which only allows entering people who older than eighteen years. Bob is the guard who sitting in front of the club and asks Alice age. But Alice does not like to reveal her age. How Alice prove she is older than eighteen years without telling her actual age.
We can solve this problem by using hash chaining. Hashing is a function which inputs something and generates constant size output. This function is called a hash function. The interesting thing about hashing is you can calculate the hash value for a given input, but calculating the original input from given hash value is really hard. Hashing is widely used in cryptography and data structures such as hash maps. Here, I am denoting input as “x” and hash function as Hash(x). Hash chaining is nothing more than applying a hash function on the result of the previous hash function. As an example Hash(Hash(x)) generate the hash value of hashed x.
Assume Alice was twenty-three years old. Which means that Alice five years older than the minimum limit. Alice selects random seed value “x” (Any real number) and applies hash function twenty-three times. This can be denoted mathematically as Hash²³(x). Let's take this result as “Verified age”. Alice again calculates Hash⁵(x) and let's take this result as “Proof”. Now Alice sends the “Verified age” and “Proof” to the Bob. Bob start applying hash chaining with “Proof” eighteen times( Hash¹⁸(Proof) ) and check the result match with the “Verified age”. If two values are same, the Bob can let Alice in. If two value is different, then Bob can assume Alice’s statement was false.
In mathematically, we can assume Alice age is “n” and age to prove is “m”.
Finally Verified age should be same as hashing “Proof” m times.
Yao’s millionaire’s problem
Here, another interesting problem supposed by Yao. Two millionaire’s need to know who is the richest among them without revealing their assets. Can you think how do they find out who is the richest without knowing their asset?
Since millions are too large, here I will explain the solution with small values. Alice has 6$ in his purse and Bob has 8$ in his purse. Alice needs to know does Bob richer than him or not. Alice takes ten boxes that can be locked each of the boxes with its own key. Alice mark boxes from one to ten and send all ten boxes to the Bob. Bob put a slip of paper wich mention either “less than”, “larger than” or “equal” symbol by comparing his money(8$) and value of the boxes. Then Bob sends back boxes to the Alice. Alice discards all keys except the sixth box. Alice uses her key and opens the box number six and she receives the slip that mentions “larger than” symbol. Which means that Bob has more money than Alice.
Here Bob or Alice does not reveal their actual assets and finally, the can know who has more money. This solution can be extended by using cryptography to use encryption instead of using boxes with keys. However, In this case, Both parties should be honest and follow protocol correctly to find the correct solution.
Oblivious Transfer
This is another problem of zero-knowledge proof that uses a bit of mathematics. The problem is, Alice has two numbers. Bob needs to know only one of the given two number without revealing Alice which number he read. I will elaborate question as follows such that it easy to understand.
Bob is an inspector who investigating a crime that happened in Alice’s company. There are two employees in Alice office named Dave and Eve. Bob suspect Eve did the crime, but Bob does not like to tell Alice that he suspects Eve for the crime. How Bob supposed to ask details of Eve from Alice without notifying that Bob does not suspect Eve specifically.
Lets M0 and M1 are the values that Alice keep and Bob needs to read only M0 without telling Alice M0 was read. Both parties agreed on generator “g”. Alice and Bob generate random number “a” and “b” which are private for themselves. Alice calculates “A” by A = g^a and sends it to Bob. Bob calculate value “B” by either B = g^b if Bob needs to read “M0” or B = A*(g^b) if “M1” needs to read. Now Bob sends value B to the Alice and she calculates value “K0” and “K1” by K0 = Hash(B^a) and K1 = Hash( (B/A)^a). Then Alice encrypts the message “M0” and “M1” to “E1” and “E2” by using “K0” and “K1” as the key. Alice sends both “E0” and “E1” to the Bob. Now Bob calculates decryption key “K” by K = Hash(A^b) and tries to decrypt both messages. But only one message will be able to decrypt, and other not.
In this way, we can confirm that only one value read by the Bob without revealing which value was actually read.
Conclusion
Here we discuss some popular question such as Ali babas cave, Yao’s millionaire's problem, proving age etc in zero-knowledge proof and how to solve it. The main goal of the Zero knowledge proof is to prove statement without revealing the input. Proof needs to satisfy three conditions Completeness, Soundness and Zero-knowledge in order to be Zero knowledge proof. Zero knowledge proof is used in solving problems in cryptography when a user does not intend to reveal some data. It used in many application wichs include cryptocurrencies, Multiparty computation, Anonymous voting system etc.
If you like to read and learn more about security, database and cloud, follow me on the medium.
