Paper 2025/458

CAKE requires programming - On the provable post-quantum security of (O)CAKE

Abstract

We revisit the post-quantum security of Password-Authenticated Key Ex- change (PAKE) from Key Encapsulation Mechanisms (KEM), focusing on (O)CAKE. Despite extensive study, these protocols still lack a security proof against quantum adversaries. We pinpoint exactly why by identifying the precise remaining obstacle. Most game-hopping arguments extend to the quantum setting via standard QROM techniques. The difficulty lies with ideal ciphers: adaptive programming and query recording are well understood classically, but no analogous tools exist for ideal ciphers in quantum superposition. To isolate the issue, we formalize programming for PAKE via a programming simulator, which captures adaptive programming on a family of permutations from an arbitrary distribution. We prove this notion is both necessary and sufficient for a proof. For necessity, we present a meta-reduction showing that any reduction-based proof for (O)CAKE must use programming in exactly this sense. We exhibit a class of KEMs – including practical schemes such as Kyber/ML-KEM – for which any successful reduction must either program or directly break the KEM challenge. The existence of this class implies that no fully generic KEM-based PAKE proof can avoid programming. For sufficiency, we show that this is the only remaining barrier: assuming the existence of our simulator and using known QROM tools, we give a complete post-quantum security proof for OCAKE. Together, our results explain why generic KEM-based PAKEs have so far resisted quantum security proofs and pinpoint the open problem whose resolution would complete the proof.