Paper 2019/1064

Separating Symmetric and Asymmetric Password-Authenticated Key Exchange

Julia Hesse


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 symmetric PAKE since the latter is not supposed to protect the password upon compromise. In this paper, we provide three contributions: - Separating symmetric 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 symmetric PAKE, programmability is not required. Our results also rule out the existence of UC-secure asymmetric PAKE in the CRS model. - Revising the security definition. We identify and close some gaps 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-method proposed by Gentry et al. satisfies our new security notion for asymmetric PAKE. To our knowledge, this is the first formal security proof of the Omega-method in the literature. - Composable multi-party asymmetric PAKE. We showcase how our revisited security notion for 2-party asymmetric PAKE can be used to obtain asymmetric PAKE protocols in the multi-user setting and discuss important aspects for implementing such a protocol.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Password-Authenticated Key ExchangeUniversal Composability
Contact author(s)
juliahesse2 @ gmail com
2022-02-24: last of 3 revisions
2019-09-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julia Hesse},
      title = {Separating Symmetric and Asymmetric Password-Authenticated Key Exchange},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1064},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.