--- 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}