Algorithms in a Nutshell

References | 313

When All Else

Fails

No matter which question Victor asks Patti (for any flip of his coin), she can

answer his question easily, and Victor can verify her answer easily. In case Albert

wants to pose as Patti, he has two possibilities: he can construct and transmit his

own graphH, which somewhat resemblesGpatti(it could, for example have the

same numbers of vertices and edges) and for which he knows a Hamiltonian

cycle. But then if Victor the Verifier says “ShowIsomorphism,” he can’t answer.

Or Albert could relabel and transmit the vertices ofGpatti. But then if Victor the

Verifier says “ShowHamiltonianCycle,” Albert can’t answer. So Albert could fake

the protocol one half of the time. In order to be more confident, Victor could play

the protocol 100 times (it is efficient, after all). Patti would succeed easily, but the

probability that Albert could fake the protocol 100 times is 0.788*10–30.

Even if Albert observes Patti and Victor playing the game 100 times, he learns

nothing that would help him play the game in the future.

References

Armstrong, Joe,Programming Erlang: Software for a Concurrent World. Pragmatic

Bookshelf, 2007.

Berman, Kenneth and Jerome Paul,Algorithms: Sequential, Parallel, and Distributed.

Course Technology, 2004.

Christofides, Nicos, “Worst-case analysis of a new heuristic for the travelling

salesman problem,” Report 388, Graduate School of Industrial Administration,

CMU, 1976.

Knuth, Donald, “Estimating the efficiency of backtrack programs,”Mathematics

of Computation 29: 121–136, 1975.

Example 10-4. Protocol that does not reveal any information

Patti constructs graph H by randomly relabeling the vertices of G-patti

Patti transmits H to Victor

Victor flips a coin with two sides (ShowIsomorphism, ShowHamiltonianCycle)

Victor then transmits the results of the flip to Patti.

if Patti receives ShowIsomorphism

she transmits the re-labeling used to construct H

else

she transmits the Hamiltonian Cycle in H

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