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