Password-based Authenticated Key Exchange at the Cost of Diffie-Hellman

Public-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).

Speaker Details

Vinod Vaikuntanathan is a researcher in the XCG group at MSR Redmond since July 2010. In previous avatars, he was a postdoctoral fellow at IBM T.J. Watson (where he held the Josef Raviv postdoctoral fellowship from 2008-2010) and a Ph.D. student at MIT (where he was awarded the George Sprowls award for the best Ph.D. thesis in Computer Science in 2009).

Date:
Speakers:
Vinod Vaikuntanathan
Affiliation:
XCG Cryptography team
    • Portrait of Jeff Running

      Jeff Running

    • Portrait of Vinod Vaikuntanathan

      Vinod Vaikuntanathan

    • Portrait of Vinod Vaikuntanathan

      Vinod Vaikuntanathan