Proving Things With Hats
Proving Things With Hats
When you log into your bank, you may be asked for certain characters from your password. If Eve was trying to hack Bob’s account, she might guess the characters correctly, but the more times she is asked, the less chance there will be in getting the characters right, based on a random guess.
In a similar way, Victor (the verifier) might challenge Peggy (the prover) to reveal something about her secret, and every time she gets it right, Victor will increasingly trust that Peggy knows the secret. Eventually, he might define that he has prompted Peggy enough, and does not have to challenge her anymore. For a character for a password, Eve has a 1-in-26 chance of getting it right for the first prompt, and might strike lucky, but in the next character, her chances of getting two characters correct from random guessing with only be 1-in-676 (26 * 26).
The Hats Problem
In an interactive form, Victor can challenge Peggy to prove that she has a given solution, and for Victor not to see what her solution is. In Figure 1, Victor sends Peggy a puzzle and asks her to colour-in the circles so that none of the circles that are connected by the vertices have the same colour, and that only three colours are used (red, yellow and green).
Peggy then goes ahead and produces the solution in Figure 2. She then tells Victor that she has found a solution to his puzzle.
Now Peggy has to prove her solution is valid to Victor, without revealing the whole solution. For this Peggy covers all the circles with a hat, so that Victor cannot see the colours underneath. Victor is then allowed to reveal the hats that connect to a given vertex. So when Peggy reveals each vertex, if she reveals two adjacent colours, he will prove Peggy has not created a correct solution, otherwise he will prove a little more that she might have a valid solution.
With every new vertex revealed, Victor increases the likelihood that Peggy does have a valid solution. So let’s say that Victor asks for Vertex A, Peggy will show yellow and green, and then for Vertex L, she will reveal red and yellow. So how do we compute the chance of showing that Peggy is telling the truth? Well, in this case, there are 18 edges connecting the circles ($E$), and the chance of Peggy cheating Victor is (E-1)/E — 17/18 (94.4%). For the next reveal we now have 17 vertices, so that the chance of cheating is 94.1\%, and where the chance of lying is 17/18 * 16/17 and which is 88.9%. Table 1 thus outlines the probability of Peggy lying for each of the reveals. When Peggy reveals over nine vertices, and all the colours revealed are different from each other, there is more chance that Peggy is telling the truth (53.1%) than is lying (46.9%).
Conclusions
So, stop giving away your secrets, and start proving that you know your secret. Welcome to the world of Zero Knowledge Proofs … enjoy!
https://asecuritysite.com/zero
Interested in doing a PhD and ZKPs, then consider applying for this PhD position: