Password-based Authenticated Key Exchange at the Cost of Diffie-Hellman
9Public-key Cryptography was born in the 1970s with the work of Diffie and Hellman where they defined and realized a foundational primitive called key exchange. In key exchange, two parties ΓÇô Alice and Bob ΓÇô who have never met each other before, can exchange messages over a public channel and agree on a shared secret key! Although the original proposal of Diffie and Hellman is secure only against passive eavesdropping adversaries, much effort has since been devoted to developing key-exchange protocols resisting active adversaries (this is also called the ΓÇ£authenticated key exchangeΓÇ¥ problem). Active adversaries can not only listen in on the communication channel, but also interfere with it arbitrarily -- modifying, inserting or deleting messages, but also impersonating the communicating entities. To resist such malice, it is necessary for Alice and Bob to share some prior, common setup information. A variety of setup assumptions have been considered in the literature. In this talk, I will focus on a very realistic and extremely challenging setting ΓÇô one where Alice and Bob share a low-entropy password (think of an ATM pin, or a computer login password). Such a password has too little entropy to be cryptographically useful, yet we will present protocols that use the shared password to ΓÇ£bootstrapΓÇ¥ a cryptographically strong shared key. Furthermore, our protocol will expend essentially the same amount of resources as the original Diffie-Hellman protocol, while also offering protection against active adversaries. Thus, in a sense, we obtain authenticated key exchange ΓÇ£for freeΓÇ¥ in the challenging password-based setting. This is joint work with Jonathan Katz (UMD).