\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 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+
−
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 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+
−
\textit{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. If the final word agrees with what+
−
you had sent 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+
−
articles? +
−
+
−
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 possible that he was+
−
given \textit{or} as the word, but it derived from a+
−
different word. This might seem very unlikely, but at+
−
least theoretical it 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 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 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+
−
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 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}+
−
\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 Let us take a closer 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$, for example.+
−
If she knows the secret for opening the wand, 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 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+
−
in order to find out whether Alice cheats, Bob just needs to+
−
repeat this protocol many times. Each time Alice has a chance+
−
of $\frac{1}{2}$ to be lucky or being found out. Iterating+
−
this $n$ means she must be right every time and 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:+
−
+
−
\begin{itemize}+
−
\item {\bf Completeness} If Alice knows the secret, Bob+
−
      accepts Alice ``proof'' for sure. There is no error+
−
      possbile in that Bob thinks Alice cheats when she+
−
      actually knows the secret. +
−
\item {\bf Soundness} If Alice does not know the secret,+
−
      Bob accepts her ``proof'' with a very small probability.+
−
      If, as in the example above, the probability of being+
−
      able to hide cheating is $\frac{1}{2}$ in each round +
−
      it will be $\frac{1}{2}^n$ after $n$-rounds, which even+
−
      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+
−
Alice has convinced Bob that she knows the secret and Bob+
−
filmed the whole protocol with a camera. Can he use the video+
−
to convince anybody else. After a moment thought you will+
−
agree that this is not the case. Alice and Bob might have just+
−
made is all up and colluded by Bob telling Alice beforehand+
−
which tunnel he will call. In this way it appears as if all+
−
iterations of the protocol were successful, but they prove+
−
nothing. If another person wants to find out whether Alice+
−
knows the secret, he or she would have to conduct the protocol+
−
again. This is actually the definition of a zero-knowledge +
−
proof: an independent observer cannot distinguish between+
−
a real protocol (where Alice knows the 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+
−
computer science solution? It turns out we need an NP problem+
−
for that. The main feature of an NP problem is that it is+
−
computational very hard to generate a solution, but it is very+
−
easy to check whether a given solution indeed solves the+
−
problem at hand.\footnote{The question whether $P = NP$ or not,+
−
we leave to others to speculate about.} +
−
+
−
One NP problem is the \emph{graph isomorphism problem}.+
−
+
−
\subsubsection*{Using Modular Arithmetic for ZKP Protocols}+
−
+
−
+
−
+
−
\end{document}+
−
+
−
%%% Local Variables: +
−
%%% mode: latex+
−
%%% TeX-master: t+
−
%%% End: +
−