Universally Composable Password-Based Key Exchange

Ran Canetti, Shai Halevi, Jonathan Katz, Yehuda Lindell and Phil MacKenzie


We propose and realize a definition of security for password-based key exchange within the framework of universally composable security. This means that our definition provides security guarantees under arbitrary composition with other protocols. In addition, it captures some aspects of the problem that were not adequately addressed by most prior notions. For instance, it does not assume any underlying probability distribution on passwords, nor does it assume independence between passwords chosen for use by different parties. We also formulate a definition of password-based secure channels, and show that it is achievable given password-based key exchange using the same tools that achieve standard secure channels given standard key exchange.

Our protocol that realizes the new definition of password-based key exchange is in the common reference string model and relies on standard number-theoretic assumptions. The components of our protocol can be instantiated to give a relatively efficient solution which is conceivably usable in practice. We also show that in the plain model (e.g., without a common reference string), it is impossible to meet our definition.

Conference version: Postscript, gzipped Postscript.

Back Home