[Resource Topic] 2023/1368: Towards post-quantum secure PAKE - A tight security proof for OCAKE in the BPR model

Welcome to the resource topic for 2023/1368

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

Authors: Nouri Alnahawi, Kathrin Hövelmanns, Andreas Hülsing, Silvia Ritsch, Alexander Wiesmaier


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.

ePrint: https://eprint.iacr.org/2023/1368

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .