Algorithms in a Nutshell

(^312) | Chapter 10: When All Else Fails
The following protocol assumes that the two problems of Graph Isomorphism
and Hamiltonian Cycle are too difficult to solve for large graphs:
Hamiltonian Cycle
Given a graph, is there a cycle to visit all the vertices exactly one time by
following edges, then returning to the starting vertex?
Graph Isomorphism
Given graphs G 1 =(V 1 ,E 1 ) and G 2 =(V 2 ,E 2 ), is there a relabeling of the vertices
of V 1 that corresponds to the labels of V 2 such that the graphs become
identical?
Figure 10-6 contains an example of two graphs that are isomorphic (i.e., iden-
tical) with the given relabeling.
It is highly unlikely that either of these problems admits an efficient solution for
all large instances. We use the difficulty of these problems to develop a protocol
for Patti to convince Victor of her identity over an insecure line, while being confi-
dent that Albert cannot pose as Patti in the future. Before starting the
identification process, Patti constructs a large graphGwith a Hamiltonian cycle
that she knows. She can do this by starting with a cycle on every vertex, and then
adding edges until it would be hard for another person to construct a Hamilto-
nian cycle. She then publishes this graph,Gpatti, in a public directory under her
name. Both Victor and Albert can readGpatti, but only she can construct a Hamil-
tonian cycle inGpatti.
She could prove her identity to Victor by showing him the order of vertices of a
Hamiltonian cycle, but then Albert or Victor could pretend to be Patti in the
future (her proof is not a zero-knowledge proof). She wants to convince Victor
that she knows the secret cycle, without Victor or Albert sharing her knowledge.
Example 10-4 contains her protocol.
Figure 10-6. Graph Isomorphism example
Algorithms in a Nutshell
Algorithms in a Nutshell By Gary Pollice, George T. Heineman, Stanley Selkow ISBN:
9780596516246 Publisher: O'Reilly Media, Inc.
Prepared for Ming Yi, Safari ID: [email protected]
Licensed by Ming Yi
Print Publication Date: 2008/10/21 User number: 594243
© 2009 Safari Books Online, LLC. This PDF is made available for personal use only during the relevant subscription term, subject to the Safari Terms of Service. Any other use