Binary file handouts/ho06.pdf has changed

--- a/handouts/ho06.tex	Sat Nov 08 01:53:08 2014 +0000
+++ b/handouts/ho06.tex	Sat Nov 08 02:28:30 2014 +0000
@@ -59,15 +59,15 @@
 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. 
+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 entirely possible that he was
-given \textit{or} as the word, but it derived from an entirely
+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 is a possibility. Protocols based on
+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
@@ -147,15 +147,65 @@
 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 was lucky. But if he 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 know the secret. So in order to fool Bob she
-needs to anticipate his call, and already go into this tunnel.
-This of course also does not work.
+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}
 
-\subsubsection*{Using Modular Arithmetic for ZKP}
+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}
 
 
 

Binary file slides/slides06.pdf has changed

--- a/slides/slides06.tex	Sat Nov 08 01:53:08 2014 +0000
+++ b/slides/slides06.tex	Sat Nov 08 02:28:30 2014 +0000
@@ -240,8 +240,7 @@
 \end{tabular}
 \end{center}
 
-Finding an isomorphism between two graphs is an NP-complete
-problem.
+Finding an isomorphism between two graphs is an NP problem.
 
 \end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
@@ -390,7 +389,7 @@
       fraud with one, she stops using one 
 \end{itemize}
 
-\end{frame}}
+\end{frame}
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% 
 
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%