International Association
for Cryptologic Research

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 commonly used to model and prove security of PAKE. So far, however, it is not known how to model or prove computational UC security against quantum adversaries. Even more so, if the proof makes use of 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 generically, assuming the underlying KEM satisfies common notions of ciphertext indistinguishability, anonymity, and (computational) public key uniformity. To achieve tight security bounds, we relate security of OCAKE to multi-user variants of the aforementioned properties.

We provide a full detailed proof, something often omitted in publications concerned with game-based security of PAKE. As a side-contribution, we demonstrate how to handle password guesses in a game-based proof in detail. Something we were unable to find in the existing literature.