\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: