# HG changeset patch # User Christian Urban # Date 1415493503 0 # Node ID 530b98bcc36fc0b714693448cce482512b691b39 # Parent 428952dd70530bc244c1a76c99b61c8a92f686f7 updated diff -r 428952dd7053 -r 530b98bcc36f handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r 428952dd7053 -r 530b98bcc36f handouts/ho06.tex --- a/handouts/ho06.tex Sat Nov 08 19:23:05 2014 +0000 +++ b/handouts/ho06.tex Sun Nov 09 00:38:23 2014 +0000 @@ -170,7 +170,7 @@ \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 + 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. @@ -255,15 +255,152 @@ Now the secret which Alice tries to hide is the knowledge of such an isomorphism $\sigma$ between two such graphs. But she can convince Bob whether she knows such an isomorphism for two -graphs using the same idea as in the example with Alibaba's -cave. +graphs, say $G_1$ and $G_2$, using the same idea as in the +example with Alibaba's cave. For this Alice and Bob must +follow 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 consistently +relabelling 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 important +point is that she needs to ``commit'' to this $H$, therefore +this kind of zero-knowledge protocols are called +\emph{commitment protocols}. Only after receiving $H$, Bob +will make up his mind about which isomorphism he asks +for---whether between $H$ and $G_1$ or $H$ and $G_2$. For this +he could flip a coin, since the choice should be as +unpredictable for Alice as possible. Once Alice receives the +request, she has to produce an isomorphism. If she generated +$H$ as shown in \eqref{hiso} and is asked for an isomorphism +between $H$ and $G_1$, she just sends $\sigma'$. If she had +been asked for an isomorphism between $H$ and $G_2$, she just +has to compose her secret isomorphism $\sigma$ and $\sigma'$. +The main point for the protocol is that even knowing the +isomorphism between $H$ and $G_1$ or $H$ and $G_2$, will not +make 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 some +agreed 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 an +isomorphism between $G_1$ and $G_2$. If she knows which +isomorphism Bob will ask for she can craft $H$ ins such a way +that it is isomorphism with either $G_1$ or $G_2$ (but it +cannot with both). Then in each case she would send Bob +a correct answer and he would come to the conclusion that +all is well. I let you also answer the question whether +such a protocol run between Alice and Bob would convince +a third person, say Pete. + +Since the interactive nature of the above PKZ protocol and the +correct ordering of the messages is so important for the +``correctness'' of the protocol, it might look surprising that +the same goal can also me achieved in a completely offline +manner. By this I mean Alice can publish all data at once, and +then at a later time, Bob can inspect the data and come to the +conclusion whether or not Alice knows the secret (again +without actually learning about the secret). For this +Alice 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 same +goal as the interactive variant is that Alice has no +control 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$s +in the hash values are such that it would pass an external +test. The point is that Alice can publish all this data +on 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 works +are relatively straightforward. The disadvantage is +that encoding any secret into a graph-isomorphism, while +possible, is awkward. The good news is that in fact +any NP problem can be used as part of a ZKP protocol. + \subsubsection*{Using Modular Arithmetic for ZKP Protocols} +Another NP-problem is to calculate discrete logarithms. It can +be used by choosing public numbers $A$, $B$, $p$, and private +$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 by +MITM attacks) \end{document} +http://btravers.weebly.com/uploads/6/7/2/9/6729909/zero_knowledge_technique.pdf +http://zk-ssh.cms.ac/docs/Zero_Knowledge_Prinzipien.pdf +http://www.wisdom.weizmann.ac.il/~oded/PS/zk-tut02v4.ps + %%% Local Variables: %%% mode: latex %%% TeX-master: t