
diff -r 0b9a16ddd625 -r fd4bf1a2d38d handouts/ho06.tex
--- a/handouts/ho06.tex	Thu Nov 06 17:41:55 2014 +0000
+++ b/handouts/ho06.tex	Fri Nov 07 00:25:59 2014 +0000
@@ -6,19 +6,19 @@
 \section*{Handout 6 (Zero-Knowledge Proofs)}
 
 Zero-knowledge proofs (short ZKP) solve a paradoxical puzzle:
-How to convince somebody else that one knows a secret without,
-revealing what the secret is? This sounds like a problem the
-Mad Hatter from Alice in Wonderland would occupy himself with,
-but actually there some serious and not so 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 (secret)? One way would be to
-come up with the following protocol: suppose the answer is
-\textit{folio}. Then look up the definition of that word in a
-dictionary. Say you find
+How to convince somebody else that one knows a secret, without
+revealing what the secret actually is? This sounds like a
+problem the Mad Hatter from Alice in Wonderland would occupy
+himself with, but actually there some serious and not so
+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:
 
 \begin{quote}
 ``an \textit{individual} leaf of paper or parchment, either
@@ -45,57 +45,58 @@
 \end{quote}
 
 \noindent 
-You could now go on to look up the definition of the third
+You could go on to look up the definition of the third
 non-article in this definition and so on. But let us assume
 you agreed with Bob to stop after three iterations with the
 third non-article word in the last definition, that is
 \textbf{or}. Now, instead of sending to Bob the solution
-\textit{folio}, you send to him \textit{or}. How can
-Bob verify that you know the solution? Well, once he solved
-it himself, he can use the dictionary and follow the same
-``trail'' as you did. It the final word agrees with what 
-you send him, he must infer you know the solution earlier
-than him. This protocol works like a one-way hash function 
-because \textit{or} does not give any hint as to what was
-the first word was. I leave you to think why this
-protocol avoids article words. 
+\textit{folio}, you send to him \textit{or}. 
+
+How can Bob verify that you know the solution? Well, once he
+solved it himself, he can use the dictionary and follow the
+same ``trail'' as you did. If the final word agrees with what
+you send him, he must infer you knew the solution earlier than
+him. This protocol works like a one-way hash function because
+\textit{or} does not give any hint as to what was the first
+word was. I leave you to think why this protocol avoids
+article words. 
 
 After Bob found his solution and verified that according to
 the protocol it ``maps'' also to \textit{or}, can he be
-entirely sure no cheating is going on. Not with 100\%
-certainty. It could have been entirely possible that
-he was given \textit{or} as the word but it derived
-from an entirely different word---this seems very unlikely,
-but is at least theoretical a possibility. Protocols
-based on zero-knowledge proofs will produce a similar
-result---they give an answer that might be erroneous 
-in a very small number of cases. The point is to itterate
-them long enough so that the theoretical possibility of
-cheating is negligibly small. 
+entirely sure no cheating is going on? Not with 100\%
+certainty. It could have been entirely possible that he was
+given \textit{or} as the word, but it derived from an entirely
+different word. This might seem very unlikely, but at
+least theoretical is a possibility. Protocols based on
+zero-knowledge proofs will produce a similar result---they
+give an answer that might be erroneous in a very small number
+of cases. The point is to iterate them long enough so that
+the theoretical possibility of cheating is negligibly small. 
 
 By the way, the authors of the paper ``Dismantling Megamos
 Crypto: Wirelessly Lockpicking a Vehicle Immobilizer'' who
 were barred from publishing their results used also a hash to
 prove they did the work and (presumably) managed to get into
-cars without a key. See Figure~\ref{paper}. This is very 
-similar to the method about crosswords. They like to prove
-that they did the work, but not giving out the ``solution''. 
-But this also shows what the problem with such methods
-are: yes, we can hide the secret temporarily, but if
-somebody else wants to verify it, then the secret has 
-to be made public. Bob needs to know that \textit{folio}
-is the solution before he can verify the claim that somebody
-else had the solution first. Similarly with the paper:
-we need to wait until the authors are finally allowed to 
-publish their finding in order to verify the hash. This
-might happen at some point, but equally it might never
-happen (what for example happens if the authors loose
-their copy of the paper because of a disk failure?).
-Zero-knowledge proofs, in contrast, can be immediately
-be checked, even if the secret is not public yet.
+cars without a key; see Figure~\ref{paper}. This is very
+similar to the method about crosswords: They like to prove
+that they did the work, but not giving out the ``solution''.
+But this also shows what the problem with such a method is:
+yes, we can hide the secret temporarily, but if somebody else
+wants to verify it, then the secret has to be made public. Bob
+needs to know that \textit{folio} is the solution before he
+can verify the claim that somebody else had the solution
+first. Similarly with the paper: we need to wait until the
+authors are finally allowed to publish their findings in order
+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 be checked, even if the secret is not public yet
+and never will be.
 
 \begin{figure}
 \begin{center}
+\addtolength{\fboxsep}{4mm}
 \fbox{\includegraphics[scale=0.4]{../pics/Dismantling_Megamos_Crypto.png}}
 \end{center}
 \caption{The authors of this paper used a hash in order to prove
@@ -106,10 +107,11 @@
 \subsubsection*{ZKP: An Illustrative Example}
 
 The idea behind zero-knowledge proofs is not very obvious and
-will surely take some time for you to digest. Therefore
-lets start with an illustrative example. The example will
-not be perfect, but hopefully explain the gist of the ideas.
-The example is called Alibaba's cave:
+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:
 
 \begin{center}
 \begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c}
@@ -120,11 +122,36 @@
 \end{tabular}
 \end{center}
 
-\noindent Lets have a look at the picture in Step 1:
-The cave is a loop where at the end is a magic wand.
-The point of the magic wand is that Alice knows the
-secret word for how to open it. She wants to keep here
-word secret, but wants to convince Bob that she knows it.
+\noindent Let us have a look at the picture in Step 1: The
+cave has a tunnel which forks at some point. Both forks are
+connected in a loop. At the deep end of the loop is a 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
+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$. If she knows
+the problem, 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 want 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 was lucky. But if he says she
+should emerge from $A$ then Alice is in trouble and Bob will
+find out she does not know the secret. So in order to fool Bob
+she needs a protocol that anticipate his call, and already go
+into this tunnel. 
 
 
 \end{document}




