sen-material: comparison handouts/ho06.tex

equal deleted inserted replaced

-:81a08931ecb4
+:428952dd7053
 serious applications of it. For example, if you solve
 crosswords with your friend, say Bob, you might want to
 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
 definition of \textit{folio} in a dictionary. Say you find:
 to verify the hash. This might happen at some point, but
 equally it might never happen (what for example happens if the
 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}
 \addtolength{\fboxsep}{4mm}
 \fbox{\includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png}}
 The idea behind zero-knowledge proofs is not very obvious and
 will surely take some time for you to digest. Therefore let us
 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}
 \includegraphics[scale=0.1]{../pics/alibaba1.png} &
 \includegraphics[scale=0.1]{../pics/alibaba2.png} &
 magic wand. The point of the magic wand is that Alice knows
 the secret word for how to open it. She wants to keep the word
 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
+would also find out the secret. So this does not work. To find
-first fix the rules: At the beginning Alice and Bob are
+a solution, let us first fix the rules: At the beginning Alice
-outside the cave. Alice goes in alone and takes either tunnel
+and Bob are outside the cave. Alice goes in alone and takes
-labelled $A$ in the picture, or the other one labelled $B$.
+either tunnel labelled $A$ in the picture, or the other tunnel
-She waits at the magic wand for the instructions from Bob, who
+labelled $B$. She waits at the magic wand for the instructions
-also goes into the gave and observes what happens at the fork.
+from Bob, who also goes into the gave and observes what
-He has no knowledge which tunnel Alice took and calls out
+happens at the fork. He has no knowledge which tunnel Alice
-(Step 2) that she should emerge from tunnel $A$, for example.
+took and calls out (in Step 2) that she should emerge from tunnel
-If she knows the secret for opening the wand, this will not be
+$A$, for example. If she knows the secret for opening the
-a problem for Alice. If she was already in the A-segment of
+wand, this will not be a problem for Alice. If she was already
-the tunnel, then she just comes back. If she was in the
+in the $A$-segment of the tunnel, then she just comes back. If
-B-segment of the tunnel she will say the magic work and goes
+she was in the $B$-segment of the tunnel she will say the magic
-through the wand to emerge from $A$ as requested by Bob.
+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,
 for example the $B$-segment of the tunnel. If now Bob says she
 should emerge from $B$, she is lucky. But if he says she
 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
+corresponding tunnel. This of course also does not work.
-in order to find out whether Alice cheats, Bob just needs to
+Consequently in order to find out whether Alice cheats, Bob
-repeat this protocol many times. Each time Alice has a chance
+just needs to repeat this protocol many times. Each time Alice
-of $\frac{1}{2}$ to be lucky or being found out. Iterating
+has a chance of $\frac{1}{2}$ to be lucky or being found out.
-this $n$ means she must be right every time and the
+Iterating this $n$ times means she must be right every time
-probability for this is $\frac{1}{2}^n$.
+and when cheating the probability for this is $\frac{1}{2}^n$.
 There are some interesting observations we can make about
 Alibaba's cave and the ZKP protocol between Alice and Bob:
 for small $n$ say $> 10$ is very small indeed.
 \item {\bf Zero-Knowledge} Even if Bob accepts
 the proof by Alice, he cannot convince anybody else.
 \end{itemize}
-\noindent The last property is the most interesting. Assume
+\noindent The last property is the most interesting one.
-Alice has convinced Bob that she knows the secret and Bob
+Assume Alice has convinced Bob that she knows the secret and
-filmed the whole protocol with a camera. Can he use the video
+Bob filmed the whole protocol with a camera. Can he use the
-to convince anybody else. After a moment thought you will
+video to convince anybody else? After a moment of thought, you
-agree that this is not the case. Alice and Bob might have just
+will agree that this is not the case. Alice and Bob might have
-made is all up and colluded by Bob telling Alice beforehand
+just made it all up and colluded by Bob telling Alice
-which tunnel he will call. In this way it appears as if all
+beforehand which tunnel he will call. In this way it appears
-iterations of the protocol were successful, but they prove
+as if all iterations of the protocol were successful, but they
-nothing. If another person wants to find out whether Alice
+prove nothing. If another person wants to find out whether
-knows the secret, he or she would have to conduct the protocol
+Alice knows the secret, he or she would have to conduct the
-again. This is actually the definition of a zero-knowledge
+protocol again. This is actually the formal definition of a
-proof: an independent observer cannot distinguish between
+zero-knowledge proof: an independent observer cannot
-a real protocol (where Alice knows the secret) and a fake
+distinguish between a real protocol (where Alice knows the
-one (where Bob and Alice colluded).
+secret) and a fake one (where Bob and Alice colluded).
 \subsubsection*{Using an Graph-Isomorphism Problem for ZKPs}
 Now the question is how can we translate Alibaba's cave into a
 \end{tabular}
 \end{tabular}
 \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
+of the first graph to the nodes of the second. With this
-can check: node $a$ is connected in $G_1$ with $g$, $h$ and
+mapping we can check: node $a$ is connected in $G_1$ with $g$,
-$i$. Node $a$ maps to node $1$ in $G_2$, which is connected to
+$h$ and $i$. Node $a$ maps to node $1$ in $G_2$, which is
-$2$, $4$ and $5$, which again correspond via the mapping. Let
+connected to $2$, $4$ and $5$, which again correspond via the
-us write $\sigma$ for such a table and let us write
+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
+\noindent for two isomorphic graphs ($\sigma$ being the
-easy to construct two isomorphic graphs: Start with an
+isomorphism). It is actually very easy to construct two
-arbitrary graph, re-label the nodes consistently. What
+isomorphic graphs: Start with an arbitrary graph, re-label the
-Alice need for the protocol below is to generate such
+nodes consistently. Alice will need to do this frequently
-isomorphic graphs.
+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}

changeset 296	428952dd7053
parent 295	81a08931ecb4
child 297	530b98bcc36f