1 of 18

Lec 19: Review

2 of 18

Security definitions

  • Game-based
    • Standard: Lec 3-4�[BPR00] Mihir Bellare, David Pointcheval, and Phillip Rogaway. Authenticated Key Exchange Secure Against Dictionary Attacks. In EUROCRYPT 2000.
    • No Reveal, multiple Test: Homework 1�[AFP05] Michel Abdalla, Pierre-Alain Fouque, and David Pointcheval. Password-Based Authenticated Key Exchange in the Three-Party Setting. In PKC 2005.
  • Simulation-based (but not UC)
    • [BMP00] Victor Boyko, Philip MacKenzie, and Sarvar Patel. Provably Secure Password-Authenticated Key Exchange Using Diffie-Hellman. In EUROCRYPT 2000.

3 of 18

  • Universally Composable (UC)
    • Standard: Lec 5-6�[CHK+05] Ran Canetti, Shai Halevi, Jonathan Katz, Yehuda Lindell, and Philip MacKenzie. Universally Composable Password-Based Key Exchange. In EUROCRYPT 2005.
    • Relaxed (TestPwd can be sent on completed instances):�[ABB+20] Michel Abdalla, Manuel Barbosa, Tatiana Bradley, Stanislaw Jarecki, Jonathan Katz, and Jiayu Xu. Universally Composable Relaxed Password Authenticated Key Exchange. In CRYPTO 2020.
  • Game-based PAKE has limited composability
    • [SL18] Marjan Skrobot and Jean Lancrenon. On Composability of Game-Based Password Authenticated Key Exchange. In EuroS&P 2018.

4 of 18

PAKE protocols (with idealized model)

  • Encrypted Key Exchange (EKE)
    • Protocol: Lec 2�[BM92] Steven M. Bellovin and Michael Merritt. Encrypted Key Exchange: Password-Based Protocols Secure Against Dictionary Attacks. In S&P 1992.
    • Game-based security proof:�[BPR00] Mihir Bellare, David Pointcheval, and Phillip Rogaway. Authenticated Key Exchange Secure Against Dictionary Attacks. In EUROCRYPT 2000.
    • UC-security proof: Lec 8-11�[JRX25] Jake Januzelli, Lawrence Roy, and Jiayu Xu. Under What Conditions Is Encrypted Key Exchange Actually Secure? In EUROCRYPT 2025 (to appear).

5 of 18

  • One-encryption EKE (OEKE) — 1-non-simultaneous round, 1 IC encryption (instead of 2 in EKE)
    • Protocol & game-based security proof: Lec 12�[BCP03] Emmanuel Bresson, Olivier Chevassut, and David Pointcheval. Security Proofs for an Efficient Password-Based Key Exchange. In CCS 2003.
    • UC-security proof:�[JRX25] Jake Januzelli, Lawrence Roy, and Jiayu Xu. Under What Conditions Is Encrypted Key Exchange Actually Secure? In EUROCRYPT 2025 (to appear).

6 of 18

  • SPAKE2
    • Protocol & game-based security proof: Lec 12�[AP05] Michel Abdalla and David Pointcheval. Simple Password-Based Encrypted Key Exchange Protocols. In CT-RSA 2005.
    • (Relaxed) UC-security proof:�[ABB+20] Michel Abdalla, Manuel Barbosa, Tatiana Bradley, Stanislaw Jarecki, Jonathan Katz, and Jiayu Xu. Universally Composable Relaxed Password Authenticated Key Exchange. In CRYPTO 2020.

7 of 18

  • CPace
    • Protocol:�[HL19] Björn Haase and Benoît Labrique. AuCPace: Efficient verifier-based PAKE protocol tailored for the IIoT. In CHES 2019.
    • (Relaxed) UC-security proof:�[AHH21] Michel Abdalla, Björn Haase, and Julia Hesse. Security Analysis of CPace. In ASIACRYPT 2021.

8 of 18

  • SPEKE
    • Protocol:�[Jablon96] David Jablon. Strong Password-Only Authenticated Key Exchange. In CCR 1996.
    • (Relaxed) UC-security proof:�[ABB+20] Michel Abdalla, Manuel Barbosa, Tatiana Bradley, Stanislaw Jarecki, Jonathan Katz, and Jiayu Xu. Universally Composable Relaxed Password Authenticated Key Exchange. In CRYPTO 2020.

9 of 18

PAKE protocols (CRS-only)

  • 3-message flow (“relaxed” SPHF, projection key depends on statement)
    • Monolith protocol:�[KOY01] Jonathan Katz, Rafael Ostrovsky, and Moti Yung. Efficient Password-Authenticated Key Exchange Using Human-Memorable Passwords. In EUROCRYPT 2001.
    • SPHF abstraction:�[GL03] Rosario Gennaro and Yehuda Lindell. A Framework for Password-Based Authenticated Key Exchange. In EUROCRYPT 2003.
    • Making it UC-secure:�[CHK+05] Ran Canetti, Shai Halevi, Jonathan Katz, Yehuda Lindell, and Philip MacKenzie. Universally Composable Password-Based Key Exchange. In EUROCRYPT 2005.

​

10 of 18

  • 3-message flow (better efficiency + explicit authentication)
    • Monolith protocol:�[JG04] Shaoquan Jiang and Guang Gong. Password Based Key Exchange with Mutual Authentication. In SAC 2004.
    • SPHF abstraction:�[GK10] Adam Groce and Jonathan Katz. A New Framework for Password-Based Authenticated Key Exchange. In CCS 2010.

11 of 18

  • 1-simultaneous round (“standard” SPHF, projection key does not depend on statement)
    • Based on Naor-Yung SPHF: Lec 14�[KV11] Jonathan Katz and Vinod Vaikuntanathan. Round-Optimal Password-Based Authenticated Key Exchange. In TCC 2011.
    • Based on Cramer-Shoup SPHF (better efficiency): Homework 3�[BBC+13] Fabrice Benhamouda, Olivier Blazy, Céline Chevalier, David Pointcheval, and Damien Vergnaud. New Techniques for SPHFs and Efficient One-Round PAKE Protocols. In CRYPTO 2013.

12 of 18

PAKE protocols (plain model)

  • Game-based (cannot achieve UC in plain model)
    • [GL01] Oded Goldreich and Yehuda Lindell. Session-Key Generation using Human Passwords Only. In CRYPTO 2001.
    • [NV04] Minh Nguyen and Salil Vadhan. Simpler Session-Key Generation from Short Random Passwords. In TCC 2004.
    • Self-composability:�[GJO10] Vipul Goyal, Abhishek Jain, and Rafail Ostrovsky. Password-Authenticated Session-Key Generation on the Internet in the Plain Model. In CRYPTO 2010.

13 of 18

Asymmetric PAKE: (UC-)security definitions

  • aPAKE Lec 16-17
    • [GMR06] Craig Gentry, Philip MacKenzie, and Zulfikar Ramzan. A Method for Making Password-Based Key Exchange Resilient to Server Compromise. In CRYPTO 2006.
  • Strong aPAKE Lec 16-17
    • [JKX18] Stanislaw Jarecki, Hugo Krawczyk, and Jiayu Xu. OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-Computation Attacks. In EUROCRYPT 2018.

14 of 18

aPAKE protocols

  •  

15 of 18

  • aPAKE based on specific PAKE protocols
    • Based on EKE (augmented EKE):�[BM93] Steven M. Bellovin and Michael Merritt. Augmented encrypted key exchange: a password-based protocol secure against dictionary attacks and password file compromise. In CCS 1993.
    • Based on SPAKE2 (SPAKE2+):�[CKS08] David Cash, Eike Kiltz, and Victor Shoup. The Twin Diffie-Hellman Problem and Applications. In EUROCRYPT 2008. (protocol)�[Shoup20] Victor Shoup. Security analysis of SPAKE2+. In TCC 2020. (relaxed UC-security proof)
    • Based on CPace (AuCPace):�[HL19] Björn Haase and Benoît Labrique. AuCPace: Efficient verifier-based PAKE protocol tailored for the IIoT. In CHES 2019.

16 of 18

  • Secure Remote Password (SRP) (only aPAKE actually used on the Internet)
    • Protocol:�[Wu98] Thomas Wu. The Secure Remote Password Protocol. In NDSS 1998.
    • UC-security proof (uses a variant of UC):�[DL24] Dennis Dayanikli and Anja Lehmann. Provable Security Analysis of the Secure Remote Password Protocol. In CSF 2024.
    • Weird design ideas, messy history; see https://blog.cryptographyengineering.com/should-you-use-srp

17 of 18

saPAKE protocols

  • OPRF + aPAKE/AKE Lec 18
    • OPAQUE (only saPAKE actually used on the Internet)�[JKX18] Stanislaw Jarecki, Hugo Krawczyk, and Jiayu Xu. OPAQUE: An Asymmetric PAKE Protocol Secure Against Pre-Computation Attacks. In EUROCRYPT 2018.
  • SPHF-based
    • [BJX19] Tatiana Bradley, Stanislaw Jarecki, and Jiayu Xu. Strong Asymmetric PAKE Based on Trapdoor CKEM. In CRYPTO 2019.
  • First agree upon a low-entropy string, then use PAKE to boost the entropy
    • [MX23] Ian McQuoid and Jiayu Xu. An Efficient Strong Asymmetric PAKE Compiler Instantiable from Group Actions. In ASIACRYPT 2023.

18 of 18

Topics we didn’t touch upon

  •