# Re: game hopping proof in password authenticated key exchange protocols

**From:** Nick Hopper (*hopper_at_cs.umn.edu*)

**Date:** 10/18/05

**Next message:**Douglas A. Gwyn: "Re: How regularly is the GnuPG source code examined?"**Previous message:**tomstdenis_at_gmail.com: "Re: ECC Patents"**In reply to:**chir0: "game hopping proof in password authenticated key exchange protocols"**Next in thread:**chir0: "Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "REPOST: Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "REPOST: Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "REPOST: Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "REPOST: Re: game hopping proof in password authenticated key exchange protocols"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]

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

**Next message:**Douglas A. Gwyn: "Re: How regularly is the GnuPG source code examined?"**Previous message:**tomstdenis_at_gmail.com: "Re: ECC Patents"**In reply to:**chir0: "game hopping proof in password authenticated key exchange protocols"**Next in thread:**chir0: "Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "REPOST: Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "REPOST: Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "REPOST: Re: game hopping proof in password authenticated key exchange protocols"**Reply:**chir0: "REPOST: Re: game hopping proof in password authenticated key exchange protocols"**Messages sorted by:**[ date ] [ thread ] [ subject ] [ author ] [ attachment ]