# HG changeset patch # User Christian Urban # Date 1415474585 0 # Node ID 428952dd70530bc244c1a76c99b61c8a92f686f7 # Parent 81a08931ecb41d4d60141119ff9624cb25e9b7a3 updated diff -r 81a08931ecb4 -r 428952dd7053 handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r 81a08931ecb4 -r 428952dd7053 handouts/ho06.tex --- a/handouts/ho06.tex Sat Nov 08 02:51:34 2014 +0000 +++ b/handouts/ho06.tex Sat Nov 08 19:23:05 2014 +0000 @@ -15,6 +15,7 @@ convince him that you found a solution for one question, but of course you do not want to reveal the solution, as this might give Bob an advantage somewhere else in the crossword. + So how to convince Bob that you know the answer (or a secret)? One way would be to come up with the following protocol: Suppose the answer is \textit{folio}. Then look up the @@ -92,7 +93,7 @@ authors lose their copy of the paper because of a disk failure?). Zero-knowledge proofs, in contrast, can be immediately checked, even if the secret is not public yet -and never will be. +and perhaps never will be. \begin{figure} \begin{center} @@ -111,7 +112,10 @@ start with a simple illustrative example. The example will not be perfect, but hopefully explain the gist of the idea. The example is called Alibaba's cave, which graphically looks as -follows: +follows:\footnote{The example is taken from an +article titled ``How to Explain Zero-Knowledge Protocols +to Your Children'' available from +\url{http://pages.cs.wisc.edu/~mkowalcz/628.pdf}.} \begin{center} \begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c} @@ -130,19 +134,20 @@ secret, but wants to convince Bob that she knows it. One way of course would be to let Bob follow her, but then he -would also find out the secret. This does not work. So let us -first fix the rules: At the beginning Alice and Bob are -outside the cave. Alice goes in alone and takes either tunnel -labelled $A$ in the picture, or the other one labelled $B$. -She waits at the magic wand for the instructions from Bob, who -also goes into the gave and observes what happens at the fork. -He has no knowledge which tunnel Alice took and calls out -(Step 2) that she should emerge from tunnel $A$, for example. -If she knows the secret for opening the wand, this will not be -a problem for Alice. If she was already in the A-segment of -the tunnel, then she just comes back. If she was in the -B-segment of the tunnel she will say the magic work and goes -through the wand to emerge from $A$ as requested by Bob. +would also find out the secret. So this does not work. To find +a solution, let us first fix the rules: At the beginning Alice +and Bob are outside the cave. Alice goes in alone and takes +either tunnel labelled $A$ in the picture, or the other tunnel +labelled $B$. She waits at the magic wand for the instructions +from Bob, who also goes into the gave and observes what +happens at the fork. He has no knowledge which tunnel Alice +took and calls out (in Step 2) that she should emerge from tunnel +$A$, for example. If she knows the secret for opening the +wand, this will not be a problem for Alice. If she was already +in the $A$-segment of the tunnel, then she just comes back. If +she was in the $B$-segment of the tunnel she will say the magic +word and goes through the wand to emerge from $A$ as requested +by Bob. Let us have a look at the case where Alice cheats, that is not knows the secret. She would still go into the cave and use, @@ -151,12 +156,12 @@ should emerge from $A$ then Alice is in trouble: Bob will find out she does not actually know the secret. So in order to fool Bob she needs to anticipate his call, and already go into the -corresponding tunnel. This of course also does not work. So -in order to find out whether Alice cheats, Bob just needs to -repeat this protocol many times. Each time Alice has a chance -of $\frac{1}{2}$ to be lucky or being found out. Iterating -this $n$ means she must be right every time and the -probability for this is $\frac{1}{2}^n$. +corresponding tunnel. This of course also does not work. +Consequently in order to find out whether Alice cheats, Bob +just needs to repeat this protocol many times. Each time Alice +has a chance of $\frac{1}{2}$ to be lucky or being found out. +Iterating this $n$ times means she must be right every time +and when cheating the probability for this is $\frac{1}{2}^n$. There are some interesting observations we can make about @@ -177,20 +182,20 @@ the proof by Alice, he cannot convince anybody else. \end{itemize} -\noindent The last property is the most interesting. Assume -Alice has convinced Bob that she knows the secret and Bob -filmed the whole protocol with a camera. Can he use the video -to convince anybody else. After a moment thought you will -agree that this is not the case. Alice and Bob might have just -made is all up and colluded by Bob telling Alice beforehand -which tunnel he will call. In this way it appears as if all -iterations of the protocol were successful, but they prove -nothing. If another person wants to find out whether Alice -knows the secret, he or she would have to conduct the protocol -again. This is actually the definition of a zero-knowledge -proof: an independent observer cannot distinguish between -a real protocol (where Alice knows the secret) and a fake -one (where Bob and Alice colluded). +\noindent The last property is the most interesting one. +Assume Alice has convinced Bob that she knows the secret and +Bob filmed the whole protocol with a camera. Can he use the +video to convince anybody else? After a moment of thought, you +will agree that this is not the case. Alice and Bob might have +just made it all up and colluded by Bob telling Alice +beforehand which tunnel he will call. In this way it appears +as if all iterations of the protocol were successful, but they +prove nothing. If another person wants to find out whether +Alice knows the secret, he or she would have to conduct the +protocol again. This is actually the formal definition of a +zero-knowledge proof: an independent observer cannot +distinguish between a real protocol (where Alice knows the +secret) and a fake one (where Bob and Alice colluded). \subsubsection*{Using an Graph-Isomorphism Problem for ZKPs} @@ -230,24 +235,28 @@ \end{center} \noindent The table on the right gives a mapping of the nodes -of the first graph to the nodes of the second. With this we -can check: node $a$ is connected in $G_1$ with $g$, $h$ and -$i$. Node $a$ maps to node $1$ in $G_2$, which is connected to -$2$, $4$ and $5$, which again correspond via the mapping. Let -us write $\sigma$ for such a table and let us write +of the first graph to the nodes of the second. With this +mapping we can check: node $a$ is connected in $G_1$ with $g$, +$h$ and $i$. Node $a$ maps to node $1$ in $G_2$, which is +connected to $2$, $4$ and $5$, which again correspond via the +mapping to $h$, $i$ and $g$ respectively. Let us write +$\sigma$ for such a table and let us write \[G_1 = \sigma(G_2)\] -\noindent for two isomorphic graphs. It is actually very -easy to construct two isomorphic graphs: Start with an -arbitrary graph, re-label the nodes consistently. What -Alice need for the protocol below is to generate such -isomorphic graphs. +\noindent for two isomorphic graphs ($\sigma$ being the +isomorphism). It is actually very easy to construct two +isomorphic graphs: Start with an arbitrary graph, re-label the +nodes consistently. Alice will need to do this frequently +for the protocol below. In order to be useful, we therefore +would need to consider substantially larger graphs, like +with thousand nodes. Now the secret which Alice tries to hide is the knowledge of such an isomorphism $\sigma$ between two such graphs. But she can convince Bob whether she knows such an isomorphism for two -graphs. +graphs using the same idea as in the example with Alibaba's +cave. \subsubsection*{Using Modular Arithmetic for ZKP Protocols}