arXiv:2609.39844
Natural Barriers to Quantum Extraction: On the Post-Quantum (In)security of (O)EKE and Masny-Rindal OT
James Bartusek, Jake Januzelli
Abstract
Encrypted key exchange (EKE), introduced by Bellovin and Merritt (IEEE S\&P 1992), and Masny-Rindal OT, introduced by Masny and Rindal (ACM CCS 2019), are highly-efficient methods for compiling essentially any KEM into advanced cryptographic protocols, namely password-authenticated key exchange (PAKE) and oblivious transfer (OT), by relying only on idealized symmetric-key primitives. They have become leading candidates for practically-implementable PAKE and OT due to (1) their simplicity, (2) their plug-and-play nature, allowing for flexibility in the choice of KEM, and (3) existing proofs of UC-security (in the classical adversarial model). Due to point (2) above, these compilers yield attractive candidates for efficient \emph{post-quantum} PAKE and OT, especially given the recent post-quantum KEM standardization efforts. This motivates the question of whether the (UC-)security of these compilers translates to the quantum adversarial model. In this work, we show that it does not. In particular, we prove that a general family of (O)EKE protocols, as well as Masny-Rindal OT, are \emph{not} UC-secure against quantum polynomial-time adversaries, even when instantiated with a post-quantum KEM. To establish UC-insecurity, we devise an adversarial strategy that provably thwarts any attempt by the simulator to extract its input (the password in the case of PAKE, and the receiver's choice bit in the case of OT). To complement these negative results, we establish that both compilers yield certain notions of \emph{game-based} security. Along the way, we establish a novel ``advantage-tight'' one-way to hiding lemma that may be of independent interest.
AI Summary
The paper asks whether classical random-oracle UC-security proofs for KEM-based encrypted key exchange, (O)EKE, and Masny–Rindal oblivious transfer survive quantum oracle access when instantiated with post-quantum KEMs. It establishes negative simulation-security results alongside positive, weaker game-based guarantees. Masny–Rindal OT fails post-quantum simulation security for any correct KEM. Ideal-cipher and two-round-Feistel OEKE fail to realize the specified UC PAKE functionality; the attack also extends to several (O)EKE variants. The obstruction is input extraction: a simulator cannot fix the receiver’s choice bit or initiator’s password while preserving the environment’s view. The construction combines coherent honest behavior with a computationally indistinguishable dummy branch that detects measurement disturbance, using environment-held entanglement. The impossibility allows non-black-box simulators and arbitrary simulated oracle responses. Under post-quantum public-key uniformity and key unpredictability, Masny–Rindal OT satisfies a game in which predicting the sender’s output at a random index succeeds with probability at most $1/2+\operatorname{negl}$. Two-Feistel OEKE with a salted random-oracle KDF satisfies stand-alone game-based PAKE security: for password min-entropy $\gamma$, key-distinguishing advantage is at most $2^{-\gamma}+\operatorname{negl}$. Proofs use measure-and-reprogram and quantum rewinding. An advantage-tight one-way-to-hiding theorem transfers search bounds to distinguishing bounds, assuming an efficiently checkable target set and allowing polynomial runtime overhead. The attacks do not demonstrate recovery of both OT outputs or an immediate practical compromise. Concrete compositional consequences, efficient simulation-secure replacement compilers, concurrent BPR-style PAKE security, and ideal-cipher game-based security remain open.
AI tools were used to find the central idea behind the proof of \zcref[S]{thm:search-to-decision} (advantage-tight one-way to hiding) and to aid with proofreading, checking of technical details, and polishing.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.