Re: game hopping proof in password authenticated key exchange protocols

From: Nick Hopper (hopper_at_cs.umn.edu)
Date: 10/18/05


Date: Tue, 18 Oct 2005 09:14:25 -0500

On Tue, 18 Oct 2005, chir0 wrote:

> Nowadays many protocols in the password authenticated key exchange
> protocol use a game hoppng method to prove their protocol's security.
> But I can't understand the way how to use that method. Is it a good
> method to the security proof?

This method of proof reduces the task of breaking, in your example, an
authenticated key exchange protocol, to efficiently solving one or more
simpler mathematical problems. Since these problems are simple to state
and many people have tried to solve them, such proofs give us some
assurance that the more complex task of breaking the key exchange protocol
is also unlikely to be solved.

> Is there anyone who can explain why game hopping method is efficient to
> prove a protocols
> or at least let me know where are reference papers or documents

Victor Shoup has an excellent introduction to writing proofs using this
method:

http://shoup.net/papers/games.pdf

And more examples of these types of proofs can be found in Goldwasser and
Bellare's lecture notes:

http://www.cse.ucsd.edu/~mihir/papers/gb.html

And if you are really interested in the complexity-theoretic
underpinnings, Goldreich's "Foundations of Cryptography" series are a
good source:

http://www.wisdom.weizmann.ac.il/~oded/foc-book.html

(There are fairly complete "fragments" that you can download for free if
you don't want to buy the volumes)

-Nick