I am working on my zero knowledge proofs and I am looking for a good example of a real world proof of this type. An even better answer would be a Zero Knowledge Proof that shows the statement isn't true.
$\begingroup$
$\endgroup$
4
-
9$\begingroup$ What's wrong with the very nice Wikipedia example? $\endgroup$– Ben Webster ♦Commented Apr 26, 2010 at 17:44
-
$\begingroup$ @Ben Webster I'd like something real world. Like showing that a real cyrpto system keeps us safe, or is vulnerable to attack. $\endgroup$– GeorgeCommented Apr 26, 2010 at 18:06
-
7$\begingroup$ Then I fail to understand why you think mathematicians are the right people to ask. Wouldn't StackOverflow be much better for this? $\endgroup$– Ben Webster ♦Commented Apr 26, 2010 at 18:21
-
4$\begingroup$ I wish someone StackOverflow would post a math proof. $\endgroup$– GeorgeCommented Apr 26, 2010 at 18:30
Add a comment
|
8 Answers
$\begingroup$
$\endgroup$
7
The classic example, given in all complexity classes I've ever taken, is the following: Imagine your friend is color-blind. You have two billiard balls; one is red, one is green, but they are otherwise identical. To your friend they seem completely identical, and he is skeptical that they are actually distinguishable. You want to prove to him (I say "him" as most color-blind people are male) that they are in fact differently-colored. On the other hand, you do not want him to learn which is red and which is green.
Here is the proof system. You give the two balls to your friend so that he is holding one in each hand. You can see the balls at this point, but you don't tell him which is which. Your friend then puts both hands behind his back. Next, he either switches the balls between his hands, or leaves them be, with probability 1/2 each. Finally, he brings them out from behind his back. You now have to "guess" whether or not he switched the balls.
By looking at their colors, you can of course say with certainty whether or not he switched them. On the other hand, if they were the same color and hence indistinguishable, there is no way you could guess correctly with probability higher than 1/2.
If you and your friend repeat this "proof" $t$ times (for large $t$), your friend should become convinced that the balls are indeed differently colored; otherwise, the probability that you would have succeeded at identifying all the switch/non-switches is at most $2^{-t}$. Furthermore, the proof is "zero-knowledge" because your friend never learns which ball is green and which is red; indeed, he gains no knowledge about how to distinguish the balls.
answered Apr 26, 2010 at 18:12
-
31$\begingroup$ +1, by a color-blind. Just to support the assertion 'most color-blind people are male': color-blindness is caused by a recessive gene worn by the X chromosome. This is completely analogous to (but not correlated with) haemophilia. Therefore, if $p$ is the probability that a man be color-blind, the probability for women drops to $p^2$. According to Wikipedia, $p$ is close to $0.08$ and therefore $p^2$ is close to $0.005$. $\endgroup$ Commented Jan 4, 2011 at 14:33
-
4$\begingroup$ Good example. In the case that the person is actually colour-blind, what would be a non-zero-knowledge proof? I mean, how could I convince a colour-blind person a ball is green? $\endgroup$ Commented Dec 5, 2012 at 23:00
-
7$\begingroup$ @Tony: well for a non-zero-knowledge proof, you can label each ball according to its colour and give both to your friend, who conceals them and then randomly shows you either ball (so that you can't read the label), and you tell him what label it must have. Repeat. This will convince him that they are different, as before, but also that you know which one is labelled green. However you can't ever convince him that a ball is green as you could simply say the red one is, so he only learns if he believes you. $\endgroup$– GrangerCommented Dec 5, 2012 at 23:50
-
5$\begingroup$ By the way, I recently learned that this example has been attributed to Oded Goldreich: wisdom.weizmann.ac.il/~/oded/poster03.html $\endgroup$ Commented Mar 9, 2015 at 0:40
-
3$\begingroup$ What if the two balls were actually the same colour. How would you convince your colour-blind friend that they are the same colour? $\endgroup$ Commented Apr 10, 2022 at 12:35
$\begingroup$
$\endgroup$
4
An example I like is this. I think I heard it from Avi Wigderson but I can't quite remember. (I don't know who actually thought of it.) You want to prove that a graph can be properly coloured with three colours. So you draw a picture of the graph and then make six copies of that picture. You then properly colour the vertices with red, blue and green, but you also colour the other five copies of the graph in the same way but permuting the colours (so, for instance, in one of them you colour all vertices red that you previously coloured blue and all vertices blue that you previously coloured red). You now repeatedly do the following. Randomly pick one of your pictures, cover each vertex with a coin (so that its colour cannot be seen) and allow the other person to pick an edge and remove the two coins at its end vertices. The other person will obtain from this the information that those two vertices are coloured differently, but will obtain no other information about the colouring.
Now if there is no proper colouring of the graph, and you keep presenting the other person with colourings of the graph, then they can randomly choose their edges, and sooner or later, with very high probability, they will hit an edge that has the same colour at each end. (For the probability to be high, you need to go for many more steps than there are edges in the graph.) So from the fact that this never happens, they can deduce that with extremely high probability you do in fact have a proper colouring of the graph.
-
1$\begingroup$ This seems like less of a 0-knowledge proof than a $\varepsilon$-knowledge proof: if the graph has $N$ vertices and we pull way more than $N$ times, it would be possible for your friend to actually keep track of which vertices have appeared with which colors and expect, eventually, pull the same vertex, edge, triangle, etc. repeatedly and with some overlapping colors that they can use to rebuild each of the six copies from. Would take a lot of memory, though. $\endgroup$ Commented Dec 5, 2012 at 15:08
-
4$\begingroup$ @Ryan: I think it really is zero knowledge. Even if your friend runs so many trials that he's seen every edge on each of the 6 copies lots of times, he won't know which trials correspond to the same copy of the graph (except for those pairs of trials where he chose the same edge), so he won't be able to assemble the information he's seen into a coloring. $\endgroup$ Commented Dec 5, 2012 at 15:51
-
$\begingroup$ @Andreas: I think you can reassemble, if not the whole coloring, then possibly large chunks of it. For example, knowing just the colors of one edge, you can fill in the colors of any triangle containing that edge. If the graph has large triangulated pieces (which you do know just by looking at it uncolored) then you get big colored patches, which at the least reduces the effort you have to make to finish the job. Only if the graph is bipartite (i.e. has no triangles) is this truly zero knowledge, and if it's bipartite, then it's 2-colorable. Though that requires a proof :) $\endgroup$ Commented Dec 5, 2012 at 18:08
-
6$\begingroup$ @Ryan: If the graph has large triangulated patches, then, once you've colored an edge in such a patch, the coloring of the whole patch is determined (since there are only 3 colors) even without running this (allegedly) zero-knowledge protocol. So the protocol has given you no new information. Also, "bipartite" is a lot stronger than "no triangles"; it means there are no cycles of any odd length. $\endgroup$ Commented Dec 5, 2012 at 21:47
$\begingroup$
$\endgroup$
0
Demonstrating an attack on a cryptosystem is very similar to the colored balls example in Ryan's answer. Suppose Alice and Bob have a means of communicating messages and Eve wants to prove that it is insecure, without revealing the method used to exploit the system. Alice and Eve can simply agree that Alice will send a sequence of random messages to Bob. If Eve can tell Alice the contents of the messages, then with high probability Eve must have an attack on the cryptosystem.
answered Apr 26, 2010 at 18:38
$\begingroup$
$\endgroup$
1
An excellent example of such a proof is one based on Sudoku, and there's even a detailed demonstration for how to conduct it. I've done this in class a number of times to show ZKPs to students.
There's more as well, at Moni Naor's page: https://www.wisdom.weizmann.ac.il/~naor/PAPERS/sudoku_abs.html
answered Apr 27, 2010 at 3:47
-
1
$\begingroup$
$\endgroup$
4
Another classic example is this. There are two public graphs F and G. Alice knows an isomorphism from F to G. She wants to prove to Bob that F and G are isomorphic graphs, but does not wish to reveal the isomorphism. The procedure is the following. Alice permutes the labels of vertices F randomly, and reveals the graph H he's got that way. She can then compute an isomorphism from H to both F and G, but Bob can't. Bob then randomly chooses either F or G, then which Alice reveals the isomorphism from H to that graph. Repeat.
The problem with this method is that it can be used in practice only if one can generate graphs on which the graph isomorphism problem is hard to decide. That is not currently the case, and might not ever be, if eg. graph isomorphism can be decided efficiently.
-
4$\begingroup$ This comment is a bit late, but I don't understand the "problem"-part. Are you saying that it is not zero-knowledge if graph isomorphism is easy? What does the hardness of graph isomorphism have to do with whether (1) the proof convinces the verifier that he knows an isomorphism, and (2) the prover learns nothing from the proof? (Sure, if graph isomorphism is easy, Bob can find Alice's secret, but the same holds true for ZKP for e.g. proving knowledge of a discrete logarithm.) $\endgroup$– TMMCommented Feb 18, 2017 at 11:06
-
$\begingroup$ If Alice has isomorphisms $a: F \rightarrow G$ and $h: H \rightarrow F$, and in response to Bob reveals either $\text{id}\circ h = h$ or $a' = a\circ h$, why can't Bob simply reconstruct $a$ as $a' \circ h^{-1}$? $\endgroup$ Commented Jun 3, 2018 at 12:23
-
2$\begingroup$ @NicolasSchmidt I think it's because in each round of protocol, Bob only can either access one of those; but not both at the same time. Next round Alice sends a different random permutation so, Bob can't reconstruct. $\endgroup$ Commented Nov 11, 2018 at 19:53
-
$\begingroup$ @kuroop Yes, you're right: the graph
His chosen at random in each round. $\endgroup$ Commented Jan 27, 2019 at 0:22
$\begingroup$
$\endgroup$
1
Most of the examples given above are nice textbook examples of ZK proofs meant for students. Here's something I'd call more a "real life" example. Assume that Alice has a secret key $x$ and public key $y = g^x$. (Here we assume that $g$ generates a group $G$ of size $p$, for large prime $p$.) She wants to convince Bob that she knows $x$ without revealing $x$. This is a typical example of an authentication/identification protocol.
A simple version of this protocol is as follows: Alice generates a new random value $r$, and sends $a = g^r$ to Bob. Bob replies with a random $k$-bit challenge $c$, and then Alice sends $z = c x + r \mod{p}$ to Bob. Bob accepts iff $g^z = y^c a$.
This is a special "challenge-response" type of protocol, also known as a $\Sigma$-protocol. The concrete protocol above was proposed by Schnorr. It is not completely ZK by itself, but it is zero knowledge if we assume that Bob is honest ($c$ is really chosen randomly).
The proof of this fact: we show by using simulation, that Bob can create $(a', c', z')$ that comes from the same distribution as the real protocol view $(a, c, z)$, but without knowing the secret key $x$. The trick is that we allow Bob to choose $c'$ and $z'$ first and then to choose $a$ so that the verification equation will accept.
Namely, the simulator creates random $c'$ and $z'$, and then chooses $a' = g^{z'} / y^{c'}$. clearly, this triple $(a', c', z')$ satisfies the verification. Moreover, in the original protocol $(a, c, z)$ is a tuple of random values from $(G, \{0, 1\}^k, \mathbb{Z}_p)$ modulo the verification requirement. But so is the simulated triple.
That "honest-verifier zero knowledge" proof (also a clear textbook protocol by now) can be made fully zero knowledge by a few additional tricks (basically, letting Bob to "commit" to $c$ before he sees $a$ - the actual solution is slightly more complicated).
The protocol is clearly of "real life" flavor, both because it can be seen to have real applications (proving you know your secret key without revealing it = authentication) and since it is very efficient.
-
$\begingroup$ There's a good discussion of the Schnorr protocol here: blog.cryptographyengineering.com/2017/01/21/… $\endgroup$– DaveCommented Jan 26, 2017 at 22:28
$\begingroup$
$\endgroup$
3
An easy ZKP-based authentication scheme is one that uses a deck of shuffled playing cards and a paper bag:
Suppose Alice and Bob want to authenticate using the secret number "27". Alice takes the deck of cards, places her hands (with the cards) inside the bag and begins drawing card after card until she has reached the 27th card. She pulls this one card out of the bag and reveals it to herself and Bob.
Alice places the cards back on the deck in the same order she drew them (not destroying the original order).
Now it's Bob's turn. He is handed the deck of cards and hides his hands (and the counting of cards) in the paper bag. If he knows the secret number (27) then he should draw down to the 27th card and reveal the same card Alice did.
If Alice and Bob draw different cards then they did not draw the same number of cards.
One more:
Suppose Alice and Bob want to authenticate using the secret number of "27" but don't want to reveal it to one another. In this scenario they use a third party, Charlie.
Charlie randomly comes up with a number (any number will do) -- we'll say 15 -- and whispers it to Alice. Alice then adds the secret number (27) to Charlie's number (15) and whispers the total (42) to Bob.
Bob subtracts the secret number (27) from the total (42) and whispers the result (15) to Charlie.
If Charlie is read back his own number (15) then he can declare Alice and Bob have successfully authenticated.
-
1$\begingroup$ As a cryptosystem, the reliance on Alice and Bob not looking at the cards is a weakness in the first system. $\endgroup$– MaxCommented Nov 14, 2010 at 11:47
-
1$\begingroup$ It's assumed that Alice and Bob are, in the first scenario, authenticating in a face-to-face manner as to make sure no slight of hand or cheating is occurring. You're right, though, in that it is not a tamper proof system. $\endgroup$– ReyCommented Nov 17, 2010 at 0:41
-
$\begingroup$ You can generalise the second scenario. N (>=3) people want to know their average salary without telling their to anybody. The first write the sum of a big random and its salary, then everyone in turn replace the slate number with the same plus its salary.At the end it comes back to the first writer who substract the big number and announce to everybody. the total divided by the number of persons $\endgroup$ Commented Oct 7, 2020 at 18:03
$\begingroup$
$\endgroup$
1
An example of Zero Knowledge Proof in the real world is as under.
Your company has authorized you to disburse funds to people that report bugs in your system. A bug bounty hunter claims that because of a flaw in your system he can view transactions processed. The bug bounty hunter is concerned that once he reveals the flaw / issue you may not pay. You do not want to pay before you can validate that his claim of a huge bug in your system is accurate.
To satisfy both the parties, initiate two test transactions in your system for a certain amount. If the bug bounty hunter can tell you the exact amount you can validate his claims, and pay him to understand the flaw and fix it.
-
$\begingroup$ This is a proof of knowledge, not a zero-knowledge proof. A zero-knowledge proof is a way of demonstrating knowledge of a fact without revealing the fact; your proposed mechanism relies precisely on revealing the fact (the amount deposited). Also, it's not clear how it protects the bounty hunter from the company's possible refusal to pay after disclosure. $\endgroup$– LSpiceCommented Jun 3, 2018 at 20:33