\documentclass{article}\usepackage{../style}\begin{document}\fnote{\copyright{} Christian Urban, 2014}\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, withoutrevealing what the secret actually is? This sounds like aproblem the Mad Hatter from Alice in Wonderland would occupyhimself with, but actually there some serious and not soserious applications of it. For example, if you solvecrosswords with your friend, say Bob, you might want toconvince him that you found a solution for one question, butof course you do not want to reveal the solution, as thismight 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 thedefinition of \textit{folio} in a dictionary. Say you find:\begin{quote}``an \textit{individual} leaf of paper or parchment, eitherloose as one of a series or forming part of a bound volume,which is numbered on the recto or front side only.''\end{quote}\noindentTake the first non-article word in this definition,in this case \textit{individual}, and look up the definitionof 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, thatis \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 looking up the definition of the thirdnon-article in this definition and so on. But let us assumeyou agreed with Bob to stop after three iterations with thethird 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 hesolved it himself, he can use the dictionary and follow thesame ``trail'' as you did. If the final word agrees with whatyou had sent him, he must infer you knew the solution earlier thanhim. This protocol works like a one-way hash function because\textit{or} does not give any hint as to what was the firstword was. I leave you to think why this protocol avoidsarticles? After Bob found his solution and verified that according tothe protocol it ``maps'' also to \textit{or}, can he beentirely sure no cheating is going on? Not with 100\%certainty. It could have been possible that he wasgiven \textit{or} as the word, but it derived from adifferent word. This might seem very unlikely, but atleast theoretical it is a possibility. Protocols based onzero-knowledge proofs will produce a similar result---theygive an answer that might be erroneous in a very small numberof cases. The point is to iterate them long enough so thatthe theoretical possibility of cheating is negligibly small. By the way, the authors of the paper ``Dismantling MegamosCrypto: Wirelessly Lockpicking a Vehicle Immobilizer'' whowere barred from publishing their results used also a hash toprove they did the work and (presumably) managed to get intocars without a key; see Figure~\ref{paper}. This is verysimilar to the method above about crosswords: They like toprove that they did the work, but not giving out the``solution''. But this also shows what the problem with such amethod is: yes, we can hide the secret temporarily, but ifsomebody else wants to verify it, then the secret has to bemade public. Bob needs to know that \textit{folio} is thesolution before he can verify the claim of Alice that she hadthe solution first. Similarly with the car-crypto paper: weneed to wait until the authors are finally allowed to publishtheir findings in order to verify the hash. This might happenat some point, but equally it might never happen (what forexample happens if the authors lose their copy of the paperbecause of a disk failure?). Zero-knowledge proofs, incontrast, can be immediately checked, even if the secret isnot public yet and perhaps 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 provelater 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 andwill surely take some time for you to digest. Therefore let usstart with a simple illustrative example. The example will notbe perfect, but hopefully explain the gist of the idea. Theexample is called Alibaba's cave, which graphically looks as follows:\footnote{The example is taken from an article titled ``How to Explain Zero-Knowledge Protocolsto Your Children'' available from \url{http://pages.cs.wisc.edu/~mkowalcz/628.pdf}.}\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 forksare connected in a loop. At the deep end of the loop is amagic wand. The point of the magic wand is that Alice knowsthe secret word for how to open it. She wants to keep the wordsecret, but wants to convince Bob that she knows it.One way of course would be to let Bob follow her, but then hewould also find out the secret. So this does not work. To finda solution, let us first fix the rules: At the beginning Aliceand Bob are outside the cave. Alice goes in alone and takeseither tunnel labelled $A$ in the picture, or the other tunnellabelled $B$. She waits at the magic wand for the instructionsfrom Bob, who also goes into the gave and observes whathappens at the fork. He has no knowledge which tunnel Alicetook and calls out (in Step 2) that she should emerge from tunnel$A$, for example. If she knows the secret for opening thewand, this will not be a problem for Alice. If she was alreadyin the $A$-segment of the tunnel, then she just comes back. Ifshe was in the $B$-segment of the tunnel she will say the magicword and goes through the wand to emerge from $A$ as requestedby Bob.Let us have a look at the case where Alice cheats, that is notknows the secret. She would still go into the cave and use,for example the $B$-segment of the tunnel. If now Bob says sheshould emerge from $B$, she is lucky. But if he says sheshould emerge from $A$ then Alice is in trouble: Bob will findout she does not actually know the secret. So in order to foolBob she needs to anticipate his call, and already go into thecorresponding tunnel. This of course also does not work.Consequently in order to find out whether Alice cheats, Bobjust needs to repeat this protocol many times. Each time Alicehas a chance of $\frac{1}{2}$ to be lucky or being found out.Iterating this $n$ times means she must be right every timeand when cheating 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 possible 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 one.Assume Alice has convinced Bob that she knows the secret andBob filmed the whole protocol with a camera. Can he use thevideo to convince anybody else? After a moment of thought, youwill agree that this is not the case. Alice and Bob might havejust made it all up and colluded by Bob telling Alicebeforehand which tunnel he will call. In this way it appearsas if all iterations of the protocol were successful, but theyprove nothing. If another person wants to find out whetherAlice knows the secret, he or she would have to conduct theprotocol again. This is actually the formal definition of azero-knowledge proof: an independent observer cannotdistinguish between a real protocol (where Alice knows thesecret) 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 acomputer science solution? It turns out we need an NP problemfor that. The main feature of an NP problem is that it iscomputational very hard to generate a solution, but it is veryeasy to check whether a given solution indeed solves theproblem 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}. Itessentially determines whether the following two graphs, say$G_1$ and $G_2$, can be moved and stretched so that they lookexactly the same.\begin{center}\begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c}$G_1$ & $G_2$\\\raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple.png}} &\raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}&\footnotesize\begin{tabular}{rl}Graph $G_1$ & Graph $G_2$\\a & 1\\b & 6\\c & 8\\d & 3\\g & 5\\h & 2\\i & 4\\j & 7\\\end{tabular}\end{tabular}\end{center}\noindent The table on the right gives a mapping of the nodesof the first graph to the nodes of the second. With thismapping we can check: node $a$ is connected in $G_1$ with $g$,$h$ and $i$. Node $a$ maps to node $1$ in $G_2$, which isconnected to $2$, $4$ and $5$, which again correspond via themapping to $h$, $i$ and $g$ respectively. Let us write$\sigma$ for such a table and let us write\[G_1 = \sigma(G_2)\]\noindent for two isomorphic graphs ($\sigma$ being theisomorphism). It is actually very easy to construct twoisomorphic graphs: Start with an arbitrary graph, re-label thenodes consistently. Alice will need to do this frequently for the protocol below. In order to be useful, we thereforewould need to consider substantially larger graphs, likewith thousand nodes. Now the secret which Alice tries to hide is the knowledge ofsuch an isomorphism $\sigma$ between two such graphs. But shecan convince Bob whether she knows such an isomorphism for twographs, say $G_1$ and $G_2$, using the same idea as in theexample with Alibaba's cave. For this Alice and Bob mustfollow the following protocol:\begin{enumerate}\item Alice generates an isomorphic graph $H$ which she sends to Bob. \item After receiving $H$, Bob asks Alice either for an isomorphism between $G_1$ and $H$, or $G_2$ and $H$.\item Alice and Bob repeat this procedure $n$ times.\end{enumerate}\noindent In Step 1 it is important that Alice always generates a fresh isomorphic graph. As said before, this is relatively easy to generate by consistentlyrelabelling nodes. If she started from $G_1$, Alice will have generated\begin{equation}H = \sigma'(G_1)\label{hiso}\end{equation}\noindent where $\sigma'$ is the isomorphism between $H$ and$G_1$. But she could equally have started from $G_2$. In the case where $G_1$ and $G_2$ are isomorphic, if $H$ is isomorphic with $G_1$, it will also be isomorphic with $G_2$, and vice versa. After generating $H$, Alice sends it to Bob. The importantpoint is that she needs to ``commit'' to this $H$, thereforethis kind of zero-knowledge protocols are called\emph{commitment protocols}. Only after receiving $H$, Bobwill make up his mind about which isomorphism he asksfor---whether between $H$ and $G_1$ or $H$ and $G_2$. For thishe could flip a coin, since the choice should be asunpredictable for Alice as possible. Once Alice receives therequest, she has to produce an isomorphism. If she generated$H$ as shown in \eqref{hiso} and is asked for an isomorphismbetween $H$ and $G_1$, she just sends $\sigma'$. If she hadbeen asked for an isomorphism between $H$ and $G_2$, she justhas to compose her secret isomorphism $\sigma$ and $\sigma'$.The main point for the protocol is that even knowing theisomorphism between $H$ and $G_1$ or $H$ and $G_2$, will notmake the task easier to find the isomorphism between $G_1$ and$G_2$, which is the secret Alice tries to protect.In order to make it crystal clear how this protocol proceeds, let us give a version using our more formal notation for protocols:\begin{center}\begin{tabular}{lrl}0) & $A \to B:$ & $G_1$ and $G_2$\\1a) & $A \to B:$ & $H_1$ \\1b) & $B \to A:$ & produce isomorphism $G_1 \leftrightarrow H_1$? \quad(or $G_2 \leftrightarrow H_1$)\\1c) & $A \to B:$ & requested isomorphism\\2a) & $A \to B:$ & $H_2$\\2b) & $B \to A:$ & produce isomorphism $G_1 \leftrightarrow H_2$? \quad(or $G_2 \leftrightarrow H_2$)\\2c) & $A \to B:$ & requested isomorphism\\ & \ldots\\\end{tabular}\end{center}\noindent As can be seen the protocol runs for someagreed number of iterations. The $H_i$ Alice needs to produce, need to be all distinct. I let you think why?It is also crucial that in each iteration, Alice first sends$H_i$ and then Bob can decide which isomorphism he wants:either $G_1 \leftrightarrow H_i$ or $G_2 \leftrightarrow H_i$.If somehow Alice can find out before she committed to $H_i$,she can cheat. For this assume Alice does \emph{not} know anisomorphism between $G_1$ and $G_2$. If she knows whichisomorphism Bob will ask for she can craft $H$ in such a waythat it is isomorphism with either $G_1$ or $G_2$ (but itcannot with both). Then in each case she would send Boba correct answer and he would come to the conclusion thatall is well. I let you also answer the question whethersuch a protocol run between Alice and Bob would convincea third person, say Pete.Since the interactive nature of the above PKZ protocol and thecorrect ordering of the messages is so important for the``correctness'' of the protocol, it might look surprising thatthe same goal can also me achieved in a completely offlinemanner. By this I mean Alice can publish all data at once, andthen at a later time, Bob can inspect the data and come to theconclusion whether or not Alice knows the secret (againwithout actually learning about the secret). For thisAlice has to do the following:\begin{enumerate}\item Alice generates $n$ isomorphic graphs $H_{1..n}$ (they need to be all distinct)\item she feeds the $H_{1..n}$ into a hashing function (for example encoded as as matrix)\item she takes the first $n$ bits of the output: whenever the output is $0$, she shows an isomorphism with $G_1$; for $1$ she shows an isomorphism with $G_2$\end{enumerate}\noindent The reason why this works and achieves the samegoal as the interactive variant is that Alice has nocontrol over the hashing functions. It would be computationally just too hard to assemble a set of$H_{1..n}$ such that she can force where $0$s and $1$sin the hash values are such that it would pass an externaltest. The point is that Alice can publish all this dataon the comfort of her own web-page, for example, and in this way convince everybody who bothers to check. The virtue of the use of graphs and isomorphism for a zero-knowledge protocol is that the idea why it worksare relatively straightforward. The disadvantage isthat encoding any secret into a graph-isomorphism, whilepossible, is awkward. The good news is that in factany NP problem can be used as part of a ZKP protocol. \subsubsection*{Using Modular Arithmetic for ZKP Protocols}While information can be encoded into graph isomorphisms, itis not the most convenient carrier of information. Clearly itis much easier to encode information into numbers. Let us lookat zero-knowledge proofs that use numbers as secrets. For thisthe underlying NP-problem is to calculate discrete logarithms.It can be used by choosing public numbers $A$, $B$, $p$, andprivate $x$ such that\begin{center}$A^x \equiv B\; mod\; p$\end{center} \noindent holds. The secret Alice tries to keep secret is $x$.\bigskip\noindent\ldots still to be completed (for example can be attacked byMITM attacks)\subsubsection*{Further Reading}Make sure you understand what NP problemsare.\footnote{\url{http://en.wikipedia.org/wiki/NP_(complexity)}} Theyare the building blocks for zero-knowledge proofs.\end{document}http://blog.cryptographyengineering.com/2014/11/zero-knowledge-proofs-illustrated-primer.htmlhttp://btravers.weebly.com/uploads/6/7/2/9/6729909/zero_knowledge_technique.pdfhttp://zk-ssh.cms.ac/docs/Zero_Knowledge_Prinzipien.pdfhttp://www.wisdom.weizmann.ac.il/~oded/PS/zk-tut02v4.pssocialist millionares problemhttp://en.wikipedia.org/wiki/Socialist_millionairehttp://twistedoakstudios.com/blog/Post3724_explain-it-like-im-five-the-socialist-millionaire-problem-and-secure-multi-party-computation%%% Local Variables: %%% mode: latex%%% TeX-master: t%%% End: