Natural Barriers to Quantum Extraction: On the Post-Quantum (In)security of (O)EKE and Masny-Rindal OT

arXiv:2609.39844 · quant-ph, cs.CR · Submitted 2026-09-30 · Read on arXiv

Listen

Transcript

Introduction to the show: ident: Quantum Radio. Generated commentary on the latest quantum physics and condensed matter papers.

Kai: I'm Kai, and with me are Mira and Lev, guest researcher.

Mira: Today's paper: "Natural Barriers to Quantum Extraction".

Kai: Encrypted key exchange (EKE) and Masny-Rindal OT are highly efficient methods for compiling essentially any Key Encapsulation Mechanism (KEM) into advanced cryptographic protocols like Password-Authenticated Key Exchange (PAKE) and Oblivious…

Mira: First, who's behind it and why it matters.

Paper summary: Mira: To wrap up on "Natural Barriers to Quantum Extraction: On the Post-Quantum (In)security of (O)EKE and Masny-Rindal OT," the authors are highlighting that despite their classical UC-security proofs, OEKE and Masny-Rindal OT don't translate directly into security in the quantum adversarial model. Kai They show this by proving that there are structural weaknesses, like the inability to extract inputs from a simulator, which thwart any attempt to use an extractor against them.

Lev: So when we look at the title, "Natural Barriers," it implies these aren't flaws in our implementation of post-quantum KEMs themselves, but rather inherent limitations in how these compilers are constructed for protocol compilation.

Kai: That’s right; they are showing that even with strong post-quantum primitives plugged in, the compiler itself creates a barrier against quantum extraction, meaning the security doesn't hold up as expected. Mira The main implication is that relying solely on classical security proofs for these compilers isn't enough when moving into the quantum realm because of these specific simulation failures.

Lev: From a researcher perspective, this tells us we have to re-evaluate how we justify the security of compiled protocols in a quantum setting; it points toward needing stronger assumptions than just what was guaranteed classically.

Kai: It gives us a clearer picture of where the current practical candidates for PAKE and OT might fall short when subjected to a quantum attacker, which is important context for anyone building systems with these primitives. Mira The authors are essentially saying that we can't just plug in any post-quantum KEM and expect the resulting protocol to inherit all its security guarantees automatically.

Conclusion: Kai: That title really hits home because it sounds like these aren't just simple bugs in the code, but fundamental structural walls that exist within the way these compilation methods are set up.

Mira: I agree with Kai; it suggests a limitation in the design of OEKE and Masny-Rindal OT that surfaces specifically when you consider quantum adversaries trying to pull out secret bits.

Lev: From my side, if these barriers are real, it means that even if we could build a perfect quantum computer, the protocol itself has a built-in mechanism that prevents an attacker from extracting the input without some kind of luck or specific error in the system.

Kai: Exactly; it’s about proving there’s a barrier against any attempt by an extractor to get the password or choice bit out of these schemes.

Mira: And what's interesting is that this doesn't just apply to one type of KEM; it shows a general family of these compilers has this issue, which is pretty big for the whole field.

Lev: If we think about running this on real hardware, it means we can’t just assume that because the underlying primitives are secure against quantum attacks, the resulting compiled protocol will automatically be secure in the same way.

Kai: So these results point toward a need to look beyond just the math of the KEM and really scrutinize how these compilers are constructed to ensure they don't inadvertently create exploitable weaknesses.

Mira: That's precisely what this work suggests; we have to be careful about what we assume about the security of compiled protocols when you move into a quantum context.

Lev: It sets a high bar for error correction research too, because if these structural flaws are real, it tells us how much overhead we might need to add just to compensate for the protocol design itself.

Kai: Right, so this isn't just about finding new quantum attacks; it's about understanding the inherent limitations of the compilation process itself when facing a quantum adversary.

Mira: Indeed, this paper lays out that specific structural weaknesses are present in OEKE and Masny-Rindal OT that prevent them from achieving certain levels of simulation-based security against quantum adversaries.

Lev: It's a sobering thought for anyone trying to deploy these protocols in a real system where you have to account for the actual computational power and noise limitations of the hardware.

Kai: It makes me wonder what this means practically for building next-generation secure communication channels that rely on these advanced techniques.

James Bartusek, Jake Januzelli

Columbia University

quant-ph, cs.CR

Submitted: 2026-09-30

Updated: 2026-09-30

Code: https://github.com/fancy-cryptography/fancy-cryptography

License: http://creativecommons.org/publicdomain/zero/1.0/

Importance score: 60/100

The gist: Encrypted key exchange (EKE) and Masny-Rindal OT are highly efficient methods for compiling essentially any Key Encapsulation Mechanism (KEM) into advanced cryptographic protocols like

Key concepts

Universally Composable (UC)-secure: This term describes a strong security property where any protocol built using the underlying component (like a KEM) is also secure. The paper shows that OEKE and Masny-Rindal OT fail this property against quantum adversaries, meaning they are not universally secure.
Simulation-Based Security: This security measure checks if an adversary can create a 'simulator' that mimics the real protocol's behavior without knowing the secret inputs. The authors prove that OEKE and Masny-Rindal OT fail this test in the quantum setting, indicating they are not simulation-secure.
Game-Based Security: This is a weaker security notion where security is defined by analyzing the protocol's behavior within a specific game framework. Both OEKE and Masny-Rindal OT satisfy these game-based security definitions in the quantum random oracle model, meaning they behave correctly under certain adversarial scenarios.
Advantage-Tight One-Way to Hiding: This is a mathematical lemma used to relate the advantage of distinguishing two distributions (how hard it is to tell them apart) to the advantage of a search problem. It helps prove that the protocol's security bounds translate into meaningful distinguishing limits.

Terminology

Random Oracle Model — 13× in this paper
Quantum Random Oracle Model — 9× in this paper
Oblivious Transfer — 8× in this paper
Adversarial Model — 7× in this paper · explained in 1 episode
Advantage-Tight One-Way to Hiding — 6× in this paper · explained in 1 episode
Universally Composable — 6× in this paper
Generalization — 3× in this paper · explained in 13 episodes
Key Encapsulation Mechanism — 3× in this paper
Password-Authenticated Key Exchange — 3× in this paper
Trace — 3× in this paper · explained in 2 episodes
Ancilla Qubits — 2× in this paper · explained in 1 episode
Annual Symposium on Foundations of Computer Science — 1× in this paper
Core — 1× in this paper · explained in 2 episodes
OEKE in the Quantum Ideal Cipher Model — 1× in this paper
Once Encrypted Key Exchange — 1× in this paper
Trace Distance — 1× in this paper · explained in 3 episodes

Summary

Encrypted key exchange (EKE) and Masny-Rindal OT are highly efficient methods for compiling essentially any Key Encapsulation Mechanism (KEM) into advanced cryptographic protocols like Password-Authenticated Key Exchange (PAKE) and Oblivious Transfer (OT). This work demonstrates that these compilers, specifically OEKE and Masny-Rindal OT, are not Universally Composable (UC)-secure against quantum polynomial-time adversaries, even when instantiated with post-quantum KEMs. The authors establish this insecurity by devising an adversarial strategy that provably thwarts a simulator's ability to extract the input (password or choice bit), while simultaneously showing that both protocols satisfy certain notions of game-based security in the quantum random oracle model.

Failure to Quantumly Extract

The core finding is that a general family of OEKE protocols and Masny-Rindal OT are not UC-secure against quantum polynomial-time adversaries, even when instantiated with a post-quantum KEM. This is established by devising 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). The paper shows that this failure stems from an inability for the simulator to extract a malicious receiver’s choice bit, which is exploited through a carefully constructed commitment scheme. The analysis involves showing that running the honest commitment strategy in equal superposition over the choice of bit yields a state where measuring registers T0, T1 produces a valid opening with probability 1/2, violating the property required for an extractor to succeed.

Simulation-Based Insecurity

The authors prove that both compilers yield certain notions of game-based security, but they do not satisfy simulation-based security against quantum adversaries. For Masny-Rindal OT, the protocol is shown to be not post-quantum simulation-secure because the sender can compute two candidate public keys and distinguish them from a uniformly random one if the KEM does not have computationally uniform public keys. For OEKE, instantiated with an ideal cipher or a 2-Feistel network, Theorem 4.4 demonstrates that the protocol does not post-quantum UC-realize FPAKE-ea. This is achieved by constructing an environment Z0 and Z1 that distinguishes between the real world (where P2 outputs their key) and the ideal world (where a simulator S interacts with an ideal functionality FOT), showing that in the real world, the distinguisher outputs 1 with probability 1, while in the ideal world, it is bounded by a term related to computational public key uniformity.

Game-Based Security Results

Despite the failure of simulation-based security, both protocols satisfy certain notions of game-based security. For Masny-Rindal OT, Theorem 5.1 proves that the protocol satisfies correctness (Definition 3.11), security against malicious receiver (Definition 3.12), and security against malicious sender (Definition 3.13) in the quantum random oracle model, provided the KEM has negligible correctness error, computationally uniform public keys, and key unpredictability. For OEKE instantiated with a 2-Feistel cipher, Theorem 5.2 confirms that the protocol satisfies Correctness (Definition 3.15), Passive security (Definition 3.16), Security against malicious initiator (Definition 3.17), and Security against malicious respondent (Definition 3.18).

Advantage-Tight One-Way to Hiding

To complement the positive results, the authors establish a novel advantage-tight one-way to hiding lemma. This lemma shows that for any sampler D outputting functions H, G, S, and a quantum state ρ, the distinguishing advantage dA is upper bounded by the search advantage pB (plus an additive negligible factor): dA ≤ pB + negl(λ). This result is crucial as it allows them to translate the search bound of 2−γ + negl(λ) into a distinguishing bound, which is necessary for proving the game-based security results.

Applications and Generalization

The techniques developed are shown to apply broadly across various protocol variants. The analysis of Masny-Rindal OT demonstrates simulation-based insecurity by replacing the PRG G with a KEM's KeyGen function. Similarly, for OEKE, the attack is shown to be agnostic to the choice of (E, D) used, holding for both ideal cipher and 2-Feistel instantiations. The work concludes that these results provide a proof of concept that security of OEKE and Masny-Rindal OT can yet be redeemed in the quantum setting, though it cautions that the situation is more subtle than in the classical setting due to the breakdown of simulation-based security.

Improvements for AI systems

As a fastidious researcher, I have analyzed this paper, Natural Barriers to Quantum Extraction: On the Post-Quantum (In)security of (O)EKE and Masny-Rindal OT. The core contribution is proving that while certain post-quantum cryptographic primitives like OEKE and Masny-Rindal OT are secure in the classical Random Oracle Model (ROM), they are demonstrably insecure against quantum polynomial-time adversaries in the Quantum Random Oracle Model (QROM) due to a breakdown of simulation-based security. Crucially, it also establishes that these protocols retain certain notions of game-based security under specific conditions.

Here are the specific improvements for AI systems derived from this research:

The fundamental improvement is moving beyond classical complexity assumptions to a rigorous quantum adversarial model when evaluating the security of cryptographic primitives used in AI/ML pipelines, specifically those involving key exchange, password authentication, and oblivious transfer mechanisms.

Inference of Cryptographic Weaknesses in PAKE/OT Compilers:
Identification of Simulation-Based Security Failures in Post-Quantum Architectures:
Development of Quantum-Aware Adversarial Training and Robustness Testing:
Design of Hybrid Cryptographic Protocols for Quantum Resilience:

Specific capabilities the improved AI system can achieve:

Inference of Weaknesses in PAKE/OT Compilers (Masny-Rindal OT and OEKE):
Identification of Simulation-Based Security Failures in Post-Quantum Architectures:
Development of Quantum-Aware Adversarial Training and Robustness Testing:
Design of Hybrid Cryptographic Protocols for Quantum Resilience:

Detailed breakdown of AI System Capabilities:

Specific, Actionable Improvements:

Specific, Actionable Improvements (How the AI System is Improved):

Detailed Breakdown of AI System Capabilities (What the Improved AI System Can Do):

Inference of Weaknesses in PAKE/OT Compilers (Masny-Rindal OT and OEKE):

2.Identification of Simulation-Based Security Failures in Post-Quantum Architectures:

3.Development of Quantum-Aware Adversarial Training and Robustness Testing:

4.Design of Hybrid Cryptographic Protocols for Quantum Resilience:

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 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 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 game-based security. Along the way, we establish a novel ``advantage-tight'' one-way to hiding lemma that may be of independent interest.