Key agreement protocols constitute one of the most valuable cryptographic primitives since they allow two (or more) users to setup a private and authenticated communication channel over a public network. This paper is concerned with key agreement protocols in the symmetric trust model, wherein the shared key is a password. This setting is very appealing from the user?s perspective since two parties, in principle, can easily agree on a shared password beforehand (e.g. on the telephone). However, designing such protocols represents an interesting challenge since there is no standard way of choosing a password that achieves an optimum trade-off between usability and security. Indeed, passwords belonging to a highly structured language (including PINs - Personal Identification Numbers) are essentially equivalent to low entropy strings.

A fundamental goal is that of obtaining secure and efficient protocols, with optimum computational complexity, round complexity and communication efficiency. These properties make them ideal candidates for mobile devices.

We present a new construction (DH-BPAKE) based on the encrypted key exchange protocol of Bellovin and Merritt augmented with an efficient key confirmation round. The communication model is asynchronous, meaning that each party can simultaneously send a message to the other party. In addition, we formally prove security in a modified version of the model of Boyko et al. (which is based on the model of Shoup).