--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/handouts/ho06.tex	Wed Nov 05 12:01:05 2014 +0000
@@ -0,0 +1,135 @@
+\documentclass{article}
+\usepackage{../style}
+
+\begin{document}
+
+\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
+
+\begin{quote}
+``an \textit{individual} leaf of paper or parchment, either
+loose as one of a series or forming part of a bound volume,
+which is numbered on the recto or front side only.''
+\end{quote}
+
+\noindent
+Take the first non-article word in this definition,
+in this case \textit{individual}, and look up the definition
+of this word, say
+
+\begin{quote}
+``a single \textit{human} being as distinct from a group''
+\end{quote}
+
+\noindent 
+In this definition take the second non-article word, that
+is \textit{human}, and again look up the definition of this 
+word. This will yield
+
+\begin{quote}
+``relating to \textit{or} characteristic of humankind''
+\end{quote}
+
+\noindent 
+You could now 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. 
+
+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. 
+
+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.
+
+\begin{figure}
+\begin{center}
+\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
+later that they have managed to break into cars.\label{paper}}
+\end{figure}
+
+
+\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:
+
+\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} &
+\includegraphics[scale=0.1]{../pics/alibaba3.png} \\
+Step 1 & Step 2 & Step 3
+\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.
+
+
+\end{document}
+
+%%% Local Variables: 
+%%% mode: latex
+%%% TeX-master: t
+%%% End: