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

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

   207 essentially determines whether the following two graphs, say

   208 $G_1$ and $G_2$, can be moved and stretched so that they look

   209 exactly the same.

   210 

   211 \begin{center}

   212 \begin{tabular}{c@{\hspace{8mm}}c@{\hspace{8mm}}c}

   213 $G_1$ & $G_2$\\

   214 \raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple.png}} &

   215 \raisebox{-13mm}{\includegraphics[scale=0.4]{../pics/simple-b.png}}&

   216 

   217 \footnotesize

   218 \begin{tabular}{rl}

   219 Graph $G_1$	& Graph $G_2$\\

   220 a	& 1\\

   221 b	& 6\\

   222 c	& 8\\

   223 d	& 3\\

   224 g	& 5\\

   225 h	& 2\\

   226 i  &  4\\

   227 j  & 7\\

   228 \end{tabular}

   229 \end{tabular}

   230 \end{center}

   231 

   232 \noindent The table on the right gives a mapping of the nodes

   233 of the first graph to the nodes of the second. With this we

   234 can check: node $a$ is connected in $G_1$ with $g$, $h$ and

   235 $i$. Node $a$ maps to node $1$ in $G_2$, which is connected to

   236 $2$, $4$ and $5$, which again correspond via the mapping. Let

   237 us write $\sigma$ for such a table and let us write

   238 

   239 \[G_1 = \sigma(G_2)\]

   240 

   241 \noindent for two isomorphic graphs. It is actually very 

   242 easy to construct two isomorphic graphs: Start with an

   243 arbitrary graph, re-label the nodes consistently. What

   244 Alice need for the protocol below is to generate such 

   245 isomorphic graphs.

   246 

   247 Now the secret which Alice tries to hide is the knowledge of

   248 such an isomorphism $\sigma$ between two such graphs. But she

   249 can convince Bob whether she knows such an isomorphism for two

   250 graphs.