Paper 2023/1368

Towards post-quantum secure PAKE - A tight security proof for OCAKE in the BPR model

Nouri Alnahawi, Hochschule Darmstadt
Kathrin Hövelmanns, Eindhoven University of Technology
Andreas Hülsing, Eindhoven University of Technology
Silvia Ritsch, Eindhoven University of Technology
Alexander Wiesmaier, Hochschule Darmstadt

We revisit OCAKE (ACNS 23), a generic recipe that constructs password-based authenticated key exchange (PAKE) from key encapsulation mechanisms (KEMs) in a black-box way. This allows to potentially achieve post-quantum security by instantiating the KEM with a post-quantum KEM like KYBER. It was left as an open problem to further adapt the proof such that it also holds against quantum attackers. The security proof is given in the universal composability (UC) framework, which is common for PAKE. So far, however, it is not known how to model or prove computational UC security against quantum adversaries, let alone if the proof uses idealized primitives like random oracles or ideal ciphers. To pave the way towards reasoning post-quantum security, we therefore resort to a (still classical) game-based security proof in the BPR model (EUROCRYPT 2000). We consider this a crucial stepping stone towards a full proof of post-quantum security. We prove security of (a minor variation of) OCAKE, assuming the underlying KEM satisfies notions of ciphertext indistinguishability, anonymity, and (computational) public-key uniformity. To achieve tight security bounds, we use multi-user variants of the aforementioned properties. We provide a full detailed proof – something often omitted in publications on game-based security of PAKE. As a side-contribution, we demonstrate in detail how to handle password guesses, which is something we were unable to find in the existing literature on game-based PAKE proofs.

Available format(s)
Cryptographic protocols
Publication info
Public-key cryptographypassword-based AKEPAKECAKEOCAKEpost-quantum cryptographyROMgame-based security.
Contact author(s)
nouri alnahawi @ h-da de
kathrin @ hoevelmanns net
andreas @ huelsing net
s ritsch @ tue nl
alexander wiesmaier @ h-da de
2023-10-25: revised
2023-09-12: received
See all versions
Short URL
No rights reserved


      author = {Nouri Alnahawi and Kathrin Hövelmanns and Andreas Hülsing and Silvia Ritsch and Alexander Wiesmaier},
      title = {Towards post-quantum secure {PAKE} - A tight security proof for {OCAKE} in the {BPR} model},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1368},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.