# HG changeset patch # User Christian Urban # Date 1415413710 0 # Node ID 5e8ffb58bdaa7201dc7ec60e48b20caa50848f39 # Parent 4e2eb1039ba529235a1a5c09f9b9b9367e0d9f70 updated diff -r 4e2eb1039ba5 -r 5e8ffb58bdaa handouts/ho06.pdf Binary file handouts/ho06.pdf has changed diff -r 4e2eb1039ba5 -r 5e8ffb58bdaa handouts/ho06.tex --- 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} diff -r 4e2eb1039ba5 -r 5e8ffb58bdaa slides/slides06.pdf Binary file slides/slides06.pdf has changed diff -r 4e2eb1039ba5 -r 5e8ffb58bdaa slides/slides06.tex --- 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} %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%