⚛️ quantum physics

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

This paper demonstrates that while (O)EKE and Masny-Rindal OT compilers offer efficient post-quantum candidates, they fail to achieve Universal Composability (UC) security against quantum polynomial-time adversaries due to fundamental barriers in input extraction, though they do retain certain game-based security guarantees.

Original authors: James Bartusek, Jake Januzelli

Published 2026-10-01

📖 5 min read🧠 Deep dive

CC0 1.0

Original authors: James Bartusek, Jake Januzelli

Original paper dedicated to the public domain under CC0 1.0 (http://creativecommons.org/publicdomain/zero/1.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

The digital world relies on a delicate architecture of trust, built on mathematical locks that are easy to create but incredibly difficult to pick without the right key. For decades, these locks have protected everything from private messages to financial transactions, relying on the assumption that even the fastest supercomputers would take thousands of years to break them. However, a new kind of machine is emerging: the quantum computer. Unlike traditional computers that process information in a linear sequence, these machines can explore many possibilities simultaneously, threatening to shatter the foundations of current encryption. In response, scientists have been racing to design new locks that can withstand this quantum power. A major strategy has been to take existing, efficient methods for securing passwords and secret data and simply swap out the old mathematical ingredients for new, quantum-resistant ones. The hope was that if the new ingredients were strong enough, the entire structure would remain secure.

A team of researchers has now discovered that this straightforward approach contains a hidden flaw. They examined two specific, widely used methods for securing communications: one for exchanging keys using a shared password, and another for a protocol called oblivious transfer, where one party can retrieve information from another without revealing which piece they chose. These methods are popular because they are simple, fast, and can be easily adapted to use the new quantum-resistant ingredients. The researchers proved that when these methods are used in a world where attackers have access to quantum computers, they fail a critical test of security known as simulation-based security. Specifically, the mathematical proofs that guarantee these systems work correctly in the classical world break down completely in the quantum world. The failure is not because the new ingredients are weak, nor does it necessarily mean an attacker can steal the secret data; rather, it means the way the protocols are constructed allows a quantum attacker to hide their actions in a way that classical security proofs cannot detect.

The core of the problem lies in how these protocols verify that a user is who they say they are. In the classical world, a security simulator—a theoretical tool used to prove a system is safe—can often rewind an attacker's actions to figure out what secret they were trying to hide, such as a password or a choice bit. This ability to rewind and extract the secret is essential for proving that the system is secure. The researchers demonstrated that a quantum attacker can exploit the laws of quantum mechanics to make their actions "fuzzy." By keeping their choices in a state of superposition, where they are effectively both options at once until measured, the attacker prevents the simulator from ever pinning down a single, definite secret. It is as if the attacker is wearing a cloak that makes them appear in two places at once; a classical observer trying to catch them would simply see a blur and fail to identify which path they took. Because the simulator cannot extract the secret, the mathematical proof of security collapses, leaving the system vulnerable in a way that was previously thought impossible, even though the attacker may still be unable to actually obtain the hidden messages.

Despite this negative finding, the story does not end in total failure. The researchers showed that while these protocols cannot be proven secure using the strictest, most comprehensive definition of safety, they still offer a meaningful level of protection under a different, slightly less demanding standard. They proved that even with a quantum attacker, the probability of breaking the system to learn a specific secret remains vanishingly small, provided the underlying mathematical ingredients are strong. This suggests that the protocols are not entirely broken, but rather that our understanding of how to prove they are safe needs to be updated for the quantum age. The researchers also developed a new mathematical tool to help analyze these systems, a technique that tightly links the difficulty of finding a secret to the difficulty of distinguishing between two scenarios. This tool allows them to establish that the protocols are safe against specific types of attacks, even if they cannot guarantee the same level of security as before.

The implications of this work are significant for the future of digital security. It serves as a stark reminder that simply replacing old mathematical components with new, quantum-resistant ones is not enough to guarantee safety. The structure of the protocol itself must be re-evaluated to ensure it can withstand the unique capabilities of quantum attackers. The researchers found that the specific techniques used to extract secrets in these popular protocols are fundamentally incompatible with the quantum world. This means that the community cannot rely on the existing "plug-and-play" approach for these specific systems. Instead, new designs or modifications will be required to bridge the gap between classical security proofs and quantum reality. The work highlights that the transition to a post-quantum future is not just a matter of swapping ingredients, but of fundamentally rethinking how we build and verify the locks that protect our digital lives.

Technical Summary: Natural Barriers to Quantum Extraction

Problem Statement

The transition to post-quantum cryptography typically involves replacing classical assumptions (like factoring or discrete logarithms) with quantum-resistant ones (like lattice-based KEMs). However, security proofs for complex protocols often rely on the Random Oracle Model (ROM) and specific adversarial properties, such as the ability to rewind an adversary to extract secret inputs (e.g., passwords or choice bits). While many protocols are proven secure in the classical ROM, it is an open question whether these proofs hold when the adversary has quantum access to the random oracle (Quantum Random Oracle Model, or QROM).

The community often operates under the belief that "naturally occurring" protocols secure in the ROM remain secure in the QROM if based on quantum-safe assumptions, viewing counterexamples as "completely artificial" theoretical constructs. This paper challenges that assumption by demonstrating that widely used, practical cryptographic compilers—specifically Masny-Rindal Oblivious Transfer (OT) and the (Once) Encrypted Key Exchange (OEKE) family for Password-Authenticated Key Exchange (PAKE)—fail to maintain their Universally Composable (UC) security guarantees in the QROM, even when instantiated with post-quantum Key Encapsulation Mechanisms (KEMs).

Methodology and Technical Approach

The authors employ a combination of simulation-based impossibility proofs and game-based security analyses to dissect the behavior of these protocols in the quantum setting.

1. The Core Mechanism: Failure of Extraction

The central technical insight is that the security of Masny-Rindal OT and OEKE relies on a "query-order" extraction technique. In the classical setting, a simulator can determine a malicious party's secret input (a choice bit $b$ in OT, or a password $pw$ in PAKE) by observing the order in which the adversary queries the random oracle.

Classical Logic: If an adversary queries $H(t_{1-b})$ before $H(t_b)$ , they are effectively "programming" the commitment, revealing their choice.
Quantum Failure: In the QROM, adversaries can query the random oracle in superposition. The concept of "query order" becomes ill-defined. The authors construct adversarial strategies where the malicious party maintains a coherent superposition of both possible inputs (e.g., $|0\rangle$ and $|1\rangle$ ) until the final opening stage.

2. Impossibility of Simulation (UC-Insecurity)

To prove UC-insecurity, the authors construct a specific environment (distinguisher) that interacts with a malicious party and a simulator.

The Attack Strategy: The adversary prepares a mixed state involving two branches:
1. A "real" branch where the adversary behaves coherently, maintaining a superposition of both possible secrets.
2. A "dummy" branch where the adversary uses uniform random strings instead of the PRG/KEM output.
The Distinguisher's Power: The distinguisher, knowing which branch is active, can verify if the simulator has successfully extracted the secret. In the "real" branch, the adversary's state is a superposition that allows opening either secret. In the "dummy" branch, the state is easily checkable.
The Contradiction: The authors prove that no simulator can distinguish between these branches without collapsing the adversary's state. If the simulator attempts to extract the secret (by measuring), it destroys the superposition required for the "real" branch to function correctly, causing the distinguisher to detect the simulation failure. This proves that no simulator can extract the input with high probability, violating the UC definition.

3. Game-Based Security and "Advantage-Tight" Reductions

Recognizing that simulation-based security fails, the authors investigate whether these protocols retain game-based security (e.g., indistinguishability or one-wayness).

Measure-and-Reprogram: They adapt the "measure-and-reprogram" technique (originally by DFMS) to show that while extraction fails, the protocols still satisfy certain game-based security notions against malicious receivers and initiators, provided the underlying KEM has specific properties (public-key uniformity and key unpredictability).
New Lemma (Advantage-Tight One-Way to Hiding): A significant technical contribution is a new "advantage-tight" one-way to hiding lemma. Standard one-way to hiding lemmas bound the distinguishing advantage by a function of the search probability and the number of queries ( $q$ ). The authors prove a version where the distinguishing advantage is bounded directly by the search probability (up to a negligible term), independent of the query count. This is achieved by using quantum rewinding to amplify the search probability without incurring a query-dependent penalty in the advantage bound.

Key Results

Negative Results (UC-Insecurity)

Masny-Rindal OT: The protocol is not UC-secure against quantum polynomial-time (QPT) adversaries in the QROM, even when instantiated with any KEM. The simulator cannot extract the receiver's choice bit.
OEKE (and variants): The protocol family (including ideal cipher and 2-Feistel instantiations) is not UC-secure in the QROM. The simulator cannot extract the password from a malicious initiator.
Scope: These results hold for any KEM, as the attack relies on the inability to extract the input from the superposition, a property inherent to the protocol structure rather than the specific hardness of the KEM.

Positive Results (Game-Based Security)

Masny-Rindal OT: The protocol satisfies game-based security against malicious receivers (guessing the correct message) and malicious senders (guessing the choice bit) in the QROM, assuming the KEM has post-quantum public-key uniformity and key unpredictability.
OEKE (2-Feistel variant): The protocol satisfies stand-alone game-based security against both malicious initiators and respondents in the QROM. The security bound for a malicious initiator is $1/2 + 2^{-\gamma}/2 + \text{negl}(\lambda)$ , where $\gamma$ is the min-entropy of the password.

Technical Contributions

Advantage-Tight One-Way to Hiding: A new lemma (Theorem 1.5/6.1) that establishes a search-to-decision reduction where the distinguishing advantage is upper-bounded by the search probability alone, removing the dependency on the number of queries.
Collapse-Binding: The authors demonstrate that the underlying commitment schemes used in these protocols satisfy "collapse-binding," a standard post-quantum binding notion, despite failing extractability.

Significance and Claims

The paper claims to provide the first examples of naturally occurring, practically relevant cryptographic protocols that are secure in the classical ROM but provably insecure in the QROM under the UC framework.

Challenging the "Natural" Assumption: The authors refute the belief that only "artificial" protocols suffer from the ROM-to-QROM gap. They show that widely deployed and standardized candidates (like Masny-Rindal OT and OEKE variants) are vulnerable to this specific type of quantum attack.
Implications for Standardization: The results suggest that the security of protocols relying on "query-order" extraction techniques cannot be assumed to translate to the post-quantum setting. This is particularly critical as the community moves toward standardizing PAKE and OT protocols (e.g., via IETF and CFRG).
Nuanced Security Landscape: The paper argues that while simulation-based security breaks down, these protocols are not entirely broken; they retain meaningful game-based security. This suggests a need for a more nuanced understanding of post-quantum security, where the breakdown of simulation-based security does not necessarily imply a total collapse of the protocol's utility, but does invalidate its UC guarantees.

In summary, the work serves as a cautionary tale for the post-quantum transition: simply replacing classical assumptions with quantum-resistant ones is insufficient if the protocol's security proof relies on classical adversarial properties (like rewinding and query ordering) that do not hold in the quantum regime.