62 article words. 

    62 articles? 

    67 certainty. It could have been entirely possible that he was

    67 certainty. It could have been possible that he was

    68 given \textit{or} as the word, but it derived from an entirely

    68 given \textit{or} as the word, but it derived from a

    70 least theoretical is a possibility. Protocols based on

    70 least theoretical it is a possibility. Protocols based on

   150 should emerge from $B$, she was lucky. But if he says she

   150 should emerge from $B$, she is lucky. But if he says she

   152 out she does not know the secret. So in order to fool Bob she

   152 out she does not actually know the secret. So in order to fool

   153 needs to anticipate his call, and already go into this tunnel.

   153 Bob she needs to anticipate his call, and already go into the

   154 This of course also does not work.

   154 corresponding tunnel. This of course also does not work. So

   155 in order to find out whether Alice cheats, Bob just needs to

   156 repeat this protocol many times. Each time Alice has a chance

   157 of $\frac{1}{2}$ to be lucky or being found out. Iterating

   158 this $n$ means she must be right every time and the 

   159 probability for this is $\frac{1}{2}^n$.

   160 

   161 

   162 There are some interesting observations we can make about 

   163 Alibaba's cave and the ZKP protocol between Alice and Bob:

   164 

   165 \begin{itemize}

   166 \item {\bf Completeness} If Alice knows the secret, Bob

   167       accepts Alice ``proof'' for sure. There is no error

   168       possbile in that Bob thinks Alice cheats when she

   169       actually knows the secret. 

   170 \item {\bf Soundness} If Alice does not know the secret,

   171       Bob accepts her ``proof'' with a very small probability.

   172       If, as in the example above, the probability of being

   173       able to hide cheating is $\frac{1}{2}$ in each round 

   174       it will be $\frac{1}{2}^n$ after $n$-rounds, which even

   175       for small $n$ say $> 10$ is very small indeed.

   176 \item {\bf Zero-Knowledge} Even if Bob accepts

   177       the proof by Alice, he cannot convince anybody else.

   178 \end{itemize} 

   179 

   180 \noindent The last property is the most interesting. Assume

   181 Alice has convinced Bob that she knows the secret and Bob

   182 filmed the whole protocol with a camera. Can he use the video

   183 to convince anybody else. After a moment thought you will

   184 agree that this is not the case. Alice and Bob might have just

   185 made is all up and colluded by Bob telling Alice beforehand

   186 which tunnel he will call. In this way it appears as if all

   187 iterations of the protocol were successful, but they prove

   188 nothing. If another person wants to find out whether Alice

   189 knows the secret, he or she would have to conduct the protocol

   190 again. This is actually the definition of a zero-knowledge 

   191 proof: an independent observer cannot distinguish between

   192 a real protocol (where Alice knows the secret) and a fake

   193 one (where Bob and Alice colluded).

   194 

   158 \subsubsection*{Using Modular Arithmetic for ZKP}

   198 Now the question is how can we translate Alibaba's cave into a

   199 computer science solution? It turns out we need an NP problem

   200 for that. The main feature of an NP problem is that it is

   201 computational very hard to generate a solution, but it is very

   202 easy to check whether a given solution indeed solves the

   203 problem at hand.\footnote{The question whether $P = NP$ or not,

   204 we leave to others to speculate about.} 

   205 

   206 One NP problem is the \emph{graph isomorphism problem}.

   207 

   208 \subsubsection*{Using Modular Arithmetic for ZKP Protocols}