International Association
for Cryptologic Research

Password-Authenticated Key Exchange (PAKE) is a method to establish cryptographic keys between two users sharing a low-entropy password. In its asymmetric version, one of the users acts as a server and only stores some function of the password, e.g., a hash. Upon server compromise, the adversary learns H(pw). Depending on the strength of the password, the attacker now has to invest more or less work to reconstruct pw from H(pw). Intuitively, asymmetric PAKE seems more challenging than standard (symmetric) PAKE since the latter is not supposed to protect the password upon compromise. In this paper, we provide three contributions: * Separating standard and asymmetric PAKE. We prove that a strong assumption like a programmable random oracle is necessary to achieve security of asymmetric PAKE in the Universal Composability (UC) framework. For standard PAKE, programmability is not required. Our results thus give the first formal evidence that, in the UC model, asymmetric PAKE is indeed harder to achieve than standard PAKE. * Revising the security definition. We identify and close a gap in the UC security definition of 2-party asymmetric PAKE given by Gentry, MacKenzie and Ramzan (Crypto 2006). For this, we specify a natural corruption model for server compromise attacks. We further remove an undesirable weakness that lets parties wrongly believe in security of compromised session keys. We demonstrate usefulness by proving that the $\Omega$-protocol proposed by Gentry et al. satisfies our new security notion for aPAKE. * Composable multi-party aPAKE. We demonstrate that reliance on a programmable random oracle hinders construction of multi-party aPAKE protocols from 2-party protocols via UC composition. Namely, the resulting protocols offer such strong security guarantees that they become impractical in any application. We provide guidance on how to relax composable security notions for multi-party asymmetric aPAKE to obtain useful protocols.