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