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