173       possbile in that Bob thinks Alice cheats when she

   173       possible in that Bob thinks Alice cheats when she

   258 graphs using the same idea as in the example with Alibaba's

   258 graphs, say $G_1$ and $G_2$, using the same idea as in the

   259 cave. 

   259 example with Alibaba's cave. For this Alice and Bob must

   260 follow the following protocol:

   261 

   262 \begin{enumerate}

   263 \item Alice generates an isomorphic graph $H$ which she

   264       sends to Bob. 

   265 \item After receiving $H$, Bob asks Alice either for an

   266       isomorphism between $G_1$ and $H$, or $G_2$ and $H$.

   267 \item Alice and Bob repeat this procedure $n$ times.

   268 \end{enumerate}

   269 

   270 \noindent In Step 1 it is important that Alice always 

   271 generates a fresh isomorphic graph. As said before, 

   272 this is relatively easy to generate by consistently

   273 relabelling nodes. If she started from $G_1$, Alice will 

   274 have generated

   275 

   276 \begin{equation}

   277 H = \sigma'(G_1)\label{hiso}

   278 \end{equation}

   279  

   280 \noindent where $\sigma'$ is the isomorphism between $H$ and

   281 $G_1$. But she could equally have started from $G_2$. In the 

   282 case where $G_1$ and $G_2$ are isomorphic, if $H$ is 

   283 isomorphic with $G_1$, it will also be isomorphic with 

   284 $G_2$, and vice versa. 

   285 

   286 After generating $H$, Alice sends it to Bob. The important

   287 point is that she needs to ``commit'' to this $H$, therefore

   288 this kind of zero-knowledge protocols are called

   289 \emph{commitment protocols}. Only after receiving $H$, Bob

   290 will make up his mind about which isomorphism he asks

   291 for---whether between $H$ and $G_1$ or $H$ and $G_2$. For this

   292 he could flip a coin, since the choice should be as

   293 unpredictable for Alice as possible. Once Alice receives the

   294 request, she has to produce an isomorphism. If she generated

   295 $H$ as shown in \eqref{hiso} and is asked for an isomorphism

   296 between $H$ and $G_1$, she just sends $\sigma'$. If she had

   297 been asked for an isomorphism between $H$ and $G_2$, she just

   298 has to compose her secret isomorphism $\sigma$ and $\sigma'$.

   299 The main point for the protocol is that even knowing the

   300 isomorphism between $H$ and $G_1$ or $H$ and $G_2$, will not

   301 make the task easier to find the isomorphism between $G_1$ and

   302 $G_2$, which is the secret Alice tries to protect.

   303 

   304 In order to make it crystal clear how this protocol proceeds, 

   305 let us give a version using our more formal notation for 

   306 protocols:

   307 

   308 \begin{center}

   309 \begin{tabular}{lrl}

   310 0)  & $A \to B:$ & $G_1$ and $G_2$\\

   311 1a) & $A \to B:$ & $H_1$ \\

   312 1b) & $B \to A:$ & produce isomorphism $G_1 \leftrightarrow H_1$? 

   313  \quad(or $G_2 \leftrightarrow H_1$)\\

   314 1c) & $A \to B:$ & requested isomorphism\\

   315 2a) & $A \to B:$ & $H_2$\\

   316 2b) & $B \to A:$ & produce isomorphism $G_1 \leftrightarrow H_2$? 

   317  \quad(or $G_2 \leftrightarrow H_2$)\\

   318 2c) & $A \to B:$ & requested isomorphism\\

   319     & \ldots\\

   320 \end{tabular}

   321 \end{center}

   322 

   323 \noindent As can be seen the protocol runs for some

   324 agreed number of iterations. The $H_i$ Alice needs to 

   325 produce, need to be all distinct. I let you think why?

   326 

   327 It is also crucial that in each iteration, Alice first sends

   328 $H_i$ and then Bob can decide which isomorphism he wants:

   329 either $G_1 \leftrightarrow H_i$ or $G_2 \leftrightarrow H_i$.

   330 If somehow Alice can find out before she committed to $H_i$,

   331 she can cheat. For this assume Alice does \emph{not} know an

   332 isomorphism between $G_1$ and $G_2$. If she knows which

   333 isomorphism Bob will ask for she can craft $H$ ins such a way

   334 that it is isomorphism with either $G_1$ or $G_2$ (but it

   335 cannot with both). Then in each case she would send Bob

   336 a correct answer and he would come to the conclusion that

   337 all is well. I let you also answer the question whether

   338 such a protocol run between Alice and Bob would convince

   339 a third person, say Pete.

   340  

   341 Since the interactive nature of the above PKZ protocol and the

   342 correct ordering of the messages is so important for the

   343 ``correctness'' of the protocol, it might look surprising that

   344 the same goal can also me achieved in a completely offline

   345 manner. By this I mean Alice can publish all data at once, and

   346 then at a later time, Bob can inspect the data and come to the

   347 conclusion whether or not Alice knows the secret (again

   348 without actually learning about the secret). For this

   349 Alice has to do the following:

   350 

   351 \begin{enumerate}

   352 \item Alice generates $n$ isomorphic graphs

   353       $H_{1..n}$ (they need to be all distinct)

   354 \item she feeds the $H_{1..n}$ into a hashing function

   355       (for example encoded as as matrix)

   356 \item she takes the first $n$ bits of the output:

   357       whenever the output is $0$, she shows an isomorphism

   358       with $G_1$; for $1$ she shows an isomorphism

   359       with $G_2$

   360 \end{enumerate}

   361 

   362 \noindent The reason why this works and achieves the same

   363 goal as the interactive variant is that Alice has no

   364 control over the hashing functions. It would be 

   365 computationally just too hard to assemble a set of

   366 $H_{1..n}$ such that she can force where $0$s and $1$s

   367 in the hash values are such that it would pass an external

   368 test. The point is that Alice can publish all this data

   369 on the comfort of her own web-page, for example, and 

   370 in this way convince everybody who bothers to check. 

   371 

   372 The virtue of the use of graphs and isomorphism for a 

   373 zero-knowledge protocol is that the idea why it works

   374 are relatively straightforward. The disadvantage is

   375 that encoding any secret into a graph-isomorphism, while

   376 possible, is awkward. The good news is that in fact

   377 any NP problem can be used as part of a ZKP protocol.  

   378