1 of 18

Lec 12: Variants of EKE

2 of 18

Recap: UC-security proof for EKE

  •  

3 of 18

How difficult is this proof?

  • No difficulty in “math” sense
  • Really hard to get all details right
    • 1. Must understand UC PAKE functionality
    • 2. Must think through all possible cases (there are a lot)
    • 3. In each case, must make sure reduction goes through (which random variable is (in)dependent of which variable, etc.)

4 of 18

What about game-based security of EKE?

  •  

5 of 18

  •  

6 of 18

Generalized EKE

7 of 18

  • Use any underlying KE protocol

 

decrypt, recover KE message

 

output KE key

output KE key

decrypt, recover KE message

8 of 18

  •  

9 of 18

  •  

10 of 18

One-Encryption EKE (OEKE) [BCP03]

11 of 18

  •  

 

 

 

 

 

 

 

 

 

12 of 18

EKE v. OEKE

​

​

​

​

  • Explicit authentication: if 2 parties arrive at different session keys, output ⊥
    • Standard notion (output independent keys) is implicit authentication

​

computation cost

communication cost

round complexity

explicit authentication?

EKE

2 exp + 1 IC

(both parties)

​

1-simultaneous round

none

OEKE

​

​

1-round

one-side

13 of 18

How to compare different cryptographic protocols in general?

  • Security
    • Game-based or UC? Which UC functionality?
    • Assumptions
  • Efficiency
    • Computation cost
    • Communication cost
    • Round complexity
  • Other factors (which party sends 1st message, etc.)
  • Conceptual cleanness (??)

14 of 18

Simple PAKE II (SPAKE2) [AP05]

15 of 18

  •  

 

 

 

 

 

 

 

 

16 of 18

  •  

 

 

 

 

 

 

 

 

 

17 of 18

  •  

 

 

 

 

 

 

 

 

18 of 18

References

  • [BCP03] Emmanuel Bresson, Olivier Chevassut, and David Pointcheval. Security Proofs for an Efficient Password-Based Key Exchange. In CCS 2003.
  • [AP05] Michel Abdalla and David Pointcheval. Simple Password-Based Encrypted Key Exchange Protocols. In CT-RSA 2005.
  • [ABB+20] Michel Abdalla, Manuel Barbosa, Tatiana Bradley, Stanisław Jarecki, Jonathan Katz, and Jiayu Xu. Universally Composable Relaxed Password Authenticated Key Exchange. In CRYPTO 2020.
  • [JRX25] Jake Januzelli, Lawrence Roy, and Jiayu Xu. Under What Conditions Is Encrypted Key Exchange Actually Secure? In EUROCRYPT 2025 (to appear).