Practical, provably secure password-based authenticated key exchange and password-change protocols in the standard model (the open core of Feng and Chen's 2007 weak-pseudorandomness framework)

A 2007 paper by Dengguo Feng and Weidong Chen built a modular design theory for password-based security protocols on a 'weak computational indistinguishability' notion that deliberately tolerates non-negligible (dictionary-scale) adversary advantage, and used it to derive a password-based message-transmission authenticator, a password-based session key distribution (PSKD) protocol, and a protected password-change (PPC-New) protocol. Every construction in that paper is proven secure only under ideal-cipher or random-oracle idealizations (ICM/ROM). The open problem is the one the paper leaves implicit: construct password-based session key distribution and password-change protocols that achieve the standard password-setting security goal (negligible offline dictionary-attack success, online advantage only $O(q/|D|)$ plus negligible) and are provably secure in the standard model, from standard intractability assumptions, while remaining efficient enough for practical deployment. The pure feasibility question was settled affirmatively in 2001 by impractical constructions; the literature through 2026 shows steady but incomplete progress on closing the efficiency gap, and deployed practice still relies on ROM/OPRF-based protocols.

Background

In a password-authenticated key exchange (PAKE) protocol, two parties who share only a short, human-memorable password drawn from a dictionary $D$ agree on a high-entropy session key over a network fully controlled by an adversary. Because $|D|$ is small, an adversary can always impersonate one party with probability about $1/|D|$ per active (online) guessing attempt; after $q$ online attempts the success probability $q/|D|$ is inherently non-negligible. The accepted security goal for such protocols is therefore two-sided: offline dictionary attacks (exhaustive testing of candidate passwords against recorded transcripts) must succeed only with negligible probability, while active attacks must be limited to online guessing, giving advantage $O(q/|D|)$ plus a negligible term. Achieving this requires proving that transcript data is computationally indistinguishable from random except through online interaction, which is why proofs routinely idealize hash functions or block ciphers as the random oracle model (ROM, where a hash is treated as a truly random function) or the ideal cipher model (ICM, where a block cipher is a truly random permutation).

Bellare, Canetti and Krawczyk (1998) introduced a modular methodology for key-exchange protocols: design the protocol in an authenticated model (AM) where the adversary only faithfully delivers messages, then 'compile' it into the unauthenticated model (UM) by replacing each message transmission with an authenticator protocol, with security preserved by an emulation argument. Their compiler relies on message-transmission (MT) authenticators built from signatures or MACs (message authentication codes) under authenticated high-entropy keys, and the framework does not directly apply when the only shared secret is an exhaustible password.

Feng and Chen's 2007 paper (Chinese original in Science in China Series F; English companion in the same journal) adapted this methodology to the password setting. They defined $(1-1/m(n))$-computational indistinguishability, where a distinguisher's advantage is bounded by $1/m(n)$ plus a negligible term instead of by a negligible term alone, and specialized $m(n)$ to the dictionary size $|D|$; a distribution that is weakly indistinguishable from uniform in this sense is called weakly pseudorandom. They proved a hybrid-style degradation theorem (independent samples lose a factor of $q(n)/m(n)$), related weak pseudorandom generators to weak one-way functions (functions whose inversion fails with non-negligible probability), and then defined a password-based analogue of the MT authenticator (the PMT authenticator, built from password-encrypted Diffie-Hellman exponents and message authentication codes), a compiler theorem transferring ideal-model security to the real model, a PSKD protocol generating multiple session keys, and a protected password-change protocol PPC-New that resists the 'double dictionary attack' (offline exhaustion of both old and new passwords, the attack that broke earlier password-change proposals such as Chang-Yang-Hwang, as shown by Wang, Fan and Guan) and denial-of-service weaknesses of predecessors; both protocol classes provide forward secrecy (later compromise of the password does not endanger previously established session keys). The crucial limitation — acknowledged in the paper itself through its citation of Goldreich and Lindell's 2001 standard-model protocol as too complex for practice — is that all of these constructions are proven secure only in the ROM/ICM; the paper also flags, but does not develop, the use of weak pseudorandom generators as components of other primitives such as stream ciphers.

Subsequent research settled feasibility but not practicality. Gennaro and Lindell (EUROCRYPT 2003) introduced a common-reference-string-based framework built from smooth projective hash functions (a tool for deriving a pseudorandom value from a language member without revealing the witness) that became the dominant standard-model methodology for PAKE; Katz and Vaikuntanathan (ASIACRYPT 2009) and later lattice-based works progressively improved efficiency, but standard-model constructions remained markedly costlier than idealized-model ones. Deployed practice resolved the trade-off in the opposite direction: the IRTF Crypto Forum Research Group standardized practically efficient password protocols whose proofs rely on random-oracle or OPRF (oblivious pseudorandom function, a two-party primitive by which one party obtains a pseudorandom-function evaluation on the other party's secret input without revealing it) idealizations — SPAKE2 (RFC 9382) for the balanced setting where both parties hold the password, and its augmented variants SPAKE2+ (RFC 9383) and OPAQUE (RFC 9807) for the asymmetric client-server setting where the server stores only a password-derived verifier — deliberately accepting idealized-model proofs in exchange for concrete efficiency. The tension between standard-model provability and practical cost is thus the live gap that the 2007 paper's reliance on ROM/ICM left implicit.

Problem Statement

Construct password-based security protocols — session key distribution and password change between two parties sharing only a password from a dictionary $D$ — that simultaneously achieve: (i) the standard password-setting security goal, namely that offline dictionary attacks on recorded transcripts succeed with only negligible probability and active attacks succeed with probability at most $O(q/|D|)$ plus a negligible term after $q$ online interactions; (ii) provable security in the standard model, that is, under an explicitly stated standard intractability assumption (e.g., decisional Diffie-Hellman (DDH), Learning With Errors (LWE), or a comparable one), with no random-oracle or ideal-cipher idealization; and (iii) practical efficiency, with round, communication and computation costs within an absolute constant factor of at most 4 of those of the deployed random-oracle-model password-authenticated key-exchange protocol SPAKE2 (the balanced setting where both parties hold the password), the round count being compared as a number of rounds, communication volume in bits, and computation under a single stated cost model (with any conversion between group and lattice operations given), so that the candidate and SPAKE2 are measured in the same unit on each axis. Throughout the statement, 'key exchange' and 'session key distribution' name the same key-establishment deliverable (a single session key or the source's several session keys); requirements (i)-(iii) are stated for the key-establishment deliverable, and for password change are read with (i) as its double-dictionary-attack analogue (negligible offline success against either the old or the new password, with online advantage still $O(q/|D|)$ plus negligible) and (iii) measured in the same units against a single named password-change baseline, the source's ROM/ICM protocol PPC-New (reference 2), rather than SPAKE2. This is the open core left by Feng and Chen's 2007 weak-pseudorandomness framework, whose own PMT-authenticator-based compiler, PSKD protocol and PPC-New password-change protocol all rely on ROM/ICM proofs.

References

1. Feng Dengguo (冯登国), Chen Weidong (陈伟东). 基于口令的安全协议的模块化设计与分析 (Modular design and analysis of password-based security protocols). Science in China Series F: Information Sciences (Chinese edition), 2007, 37(1): 223–237. DOI: 10.1360/zf2007-37-1-223. URL: https://www.sciengine.com/doi/10.1360/zf2007-37-1-223
2. Feng DengGuo, Chen WeiDong. Modular approach to the design and analysis of password-based security protocols. Science in China Series F: Information Sciences, 2007, 50(3): 381–398. DOI: 10.1007/s11432-007-0034-5. URL: https://link.springer.com/article/10.1007/s11432-007-0034-5
3. Bellare Mihir, Canetti Ran, Krawczyk Hugo. A modular approach to the design and analysis of authentication and key exchange protocols (extended abstract). Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC 1998), 1998, 419–428. DOI: 10.1145/276698.276854. URL: https://doi.org/10.1145/276698.276854
4. Goldreich Oded, Lindell Yehuda. Session-Key Generation Using Human Passwords Only. Advances in Cryptology – CRYPTO 2001, LNCS 2139, 2001, 408–432. DOI: 10.1007/3-540-44647-8_24. URL: https://doi.org/10.1007/3-540-44647-8_24
5. Gennaro Rosario, Lindell Yehuda. A Framework for Password-Based Authenticated Key Exchange. Advances in Cryptology – EUROCRYPT 2003, LNCS 2656, 2003, 524–543. DOI: 10.1007/3-540-39200-9_33. URL: https://doi.org/10.1007/3-540-39200-9_33. IACR ePrint 2003/032: https://eprint.iacr.org/2003/032
6. Katz Jonathan, Vaikuntanathan Vinod. Smooth Projective Hashing and Password-Based Authenticated Key Exchange from Lattices. Advances in Cryptology – ASIACRYPT 2009, LNCS 5912, 2009, 636–652. DOI: 10.1007/978-3-642-10366-7_37. URL: https://doi.org/10.1007/978-3-642-10366-7_37
7. Benhamouda Fabrice, Blazy Olivier, Chevalier Céline, Pointcheval David, Vergnaud Damien. New Techniques for SPHFs and Efficient One-Round PAKE Protocols. Advances in Cryptology – CRYPTO 2013, LNCS 8042, 2013, 449–475. DOI: 10.1007/978-3-642-40041-4_25. Full version: IACR ePrint 2015/188. URL: https://eprint.iacr.org/2015/188
8. Jiang Shaoquan, Gong Guang, He Jingnan, Nguyen Khoa, Wang Huaxiong. PAKEs: New Framework, New Techniques and More Efficient Lattice-Based Constructions in the Standard Model. Public-Key Cryptography – PKC 2020, LNCS 12110, 2020, 396–427. DOI: 10.1007/978-3-030-45374-9_14. IACR ePrint 2020/140. URL: https://eprint.iacr.org/2020/140
9. Jarecki Stanislaw, Krawczyk Hugo, Xu Jiayu. OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-Computation Attacks. Advances in Cryptology – EUROCRYPT 2018, LNCS 10822, 2018, 456–486. DOI: 10.1007/978-3-319-78372-7_15. IACR ePrint 2018/163. URL: https://eprint.iacr.org/2018/163
10. Bourdrez Dan, Krawczyk Hugo, Lewi Kevin, Wood Christopher A. The OPAQUE Augmented Password-Authenticated Key Exchange (aPAKE) Protocol. RFC 9807 (IRTF Crypto Forum Research Group), July 2025. DOI: 10.17487/rfc9807. URL: https://www.rfc-editor.org/rfc/rfc9807
11. Ladd Watson. SPAKE2, a Password-Authenticated Key Exchange. RFC 9382 (IRTF Crypto Forum Research Group), September 2023. DOI: 10.17487/rfc9382. URL: https://www.rfc-editor.org/rfc/rfc9382
12. Taubert Thomé, Wood Christopher A. SPAKE2+, an Augmented Password-Authenticated Key Exchange (PAKE) Protocol. RFC 9383 (IRTF Crypto Forum Research Group), September 2023. DOI: 10.17487/rfc9383. URL: https://www.rfc-editor.org/rfc/rfc9383
13. Wang Chih-I, Fan Chun-I, Guan Deng-Jyi. Cryptanalysis on Chang-Yang-Hwang Protected Password Change Protocol. IACR ePrint 2005/182 (2005). URL: https://eprint.iacr.org/2005/182
14. Abdolmaleki Behzad, Chakraborty Suvradip, Khazaei Shahram, Magliocco Lorenzo, Roustaeifar Nahid, Vahdani Behzad, Venturi Daniele. Round-Optimal Subversion-Resilient UC PAKE from Malleable Trapdoor Smooth Projective Hash Functions. IACR ePrint 2026/1047 (2026). URL: https://eprint.iacr.org/2026/1047