PaperlayerView exact revision on arXiv

Source-linked AI summary

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

James Bartusek, Jake Januzelli

arXiv:2609.39844v1quant-phcs.CR

TL;DR

The paper asks whether classical-ROM security for practical protocols based on post-quantum assumptions survives quantum random-oracle access. It analyzes extraction-based attacks and proves that Masny-Rindal OT and (O)EKE are not UC-secure in the QROM, while also establishing game-based security results.

  • Problem

    Whether naturally occurring protocols secure in the ROM under quantum-safe assumptions remain secure in the QROM is an open question, while existing examples were theoretical and purpose-built.

    Source: §1 · p. 3

  • Method

    The paper constructs quantum adversarial strategies that prevent simulators from extracting protocol inputs, and proves complementary game-based security results.

    Source: §1 · p. 3, §2.2 · p. 6

  • Results

    Masny-Rindal OT and (O)EKE are UC-insecure in the QROM, although both protocols satisfy some QROM game-based security notions.

    Source: §1 · p. 3, Masny-Rindal OT · p. 4

  • Takeaways & Limitations

    The results establish a separation between classical and quantum security for naturally occurring protocols based on post-quantum assumptions.

    Source: §2.5 · p. 10

    The attacks break simulation-based security but have no immediately obvious practical consequence, and the protocols retain some game-based security.

    Source: §2.6 · p. 10

Abstract

from arXiv · show

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.

1 Introduction

The paper asks whether classical ROM security of practical protocols built from post-quantum assumptions survives quantum oracle access, and shows that it does not for Masny-Rindal OT and (O)EKE. It also establishes game-based security results and an advantage-tight one-way-to-hiding lemma.

1 Introduction

  • Classical ROM proofs may rely on assumptions such as adversary rewinding [ARU14], while QROM adversaries can query random oracles in superposition.The paper notes that many QROM proofs require quantum-information expertise and can be substantially more complex than ROM proofs.Source: §1 · p. 3
  • Masny-Rindal OT and the (O)EKE family are UC-insecure in the QROM despite classical-ROM UC security.The paper presents these as naturally occurring protocols based on post-quantum assumptions.Source: §1 · p. 3, Masny-Rindal OT · p. 4
  • Both protocols nevertheless satisfy some notions of game-based security in the QROM under assumptions used for their classical-ROM proofs.Prior to this work, the authors report no fully established simulation-based or game-based security results for either protocol against quantum adversaries.Source: §1 · p. 3

Masny-Rindal OT.

  • Masny-Rindal OT is UC-secure in the ROM when instantiated with ML-KEM, but the authors show this does not hold in the QROM.The protocol is a two-message random-OT compiler from KEMs.Source: Masny-Rindal OT · pp. 3–4
  • Masny-Rindal OT instantiated with any KEM is not post-quantum simulation-secure.The attack exploits the simulator’s inability to extract a malicious receiver’s choice bit, but does not establish that the receiver obtains both sender messages.Source: Masny-Rindal OT · p. 4
  • Under public-key uniformity and key unpredictability, 2-Feistel OEKE satisfies stand-alone game-based security in the QROM against malicious initiators and respondents.This result is stated for any KEM satisfying those conditions.Source: Masny-Rindal OT · p. 5
  • The new one-way-to-hiding lemma bounds distinguishing advantage f by search probability p, up to negligible error, independently of query count or depth.It requires efficiently checkable S; the search reduction may run longer, with polynomial query-dependent blowup, and the lemma is crucial to the tight post-quantum game-based OEKE result.Source: Masny-Rindal OT · p. 5

2 Technical overview

The overview uses a commitment scheme to explain why quantum adversaries can defeat extraction even when commitments remain computationally hiding and post-quantum binding. It applies this separation to Masny-Rindal OT and OEKE, while establishing game-based security results and identifying open questions.

2.1 An illustrative commitment scheme

  • The illustrative commitment is computationally hiding, classically extractable by observing random-oracle query order, and computationally collapse-binding, but not extractable against quantum committers.Its commitment is (t0, t1), with one component formed by XORing G(sb) and a random-oracle output.Source: §2.1 · p. 6

2.2 Failure to quantumly extract

  • A dummy branch lets the distinguisher check whether extraction collapses the state, while the extractor cannot distinguish it from the coherent branch.Pseudorandomness of G supports replacing the coherent branch with the dummy branch, after which measuring the bit conflicts with the extractor’s fixed choice.Source: §2.2 · pp. 7–8

2.3 Collapse-binding

  • Measure-and-reprogram supports classical-style binding, which suffices for collapse-binding because the commitment has only one valid opening per bit.The reduction programs an external challenge into the random oracle and uses a successful pair of openings to contradict G’s pseudorandomness.Source: §2.3 · p. 8

2.4 Applications

  • For Masny-Rindal OT, no simulator can extract a malicious receiver’s choice bit by the stated argument, which requires pk computationally indistinguishable from uniform; otherwise a malicious sender’s distinguishing advantage transfers to guessing that bit.The passage says this public-key assumption comes for free: if pk were distinguishable from uniform, the OT protocol would be insecure against a malicious sender.Source: §2.4 · p. 9
  • For known OEKE variants, no simulator extracts a malicious initiator’s password; in stand-alone 2-Feistel security, prediction is bounded by 2^-δ + negl(λ).A two-password search bound and an advantage-tight one-way-to-hiding theorem support the distinguishing bound; the KEM assumption is pseudorandom public keys, also required against offline password guessing.Source: §2.4 · pp. 9–10

2.5 Discussion

  • The work separates classical and quantum adversarial models using natural, widely used commitment, PAKE, and OT constructions rather than contrived protocols.The authors place this result among methods separating the models even under post-quantum assumptions.Source: §2.5 · p. 10

2.6 Future work

  • The consequences of the simulation-security separation remain unclear, and finding broader contexts where it creates clear security issues is left open.The authors also ask whether efficient, simulation-secure QROM compilers exist for two-message OT or PAKE.Source: §2.6 · pp. 10–11
  • Full BPR security for 2-Feistel OEKE and game-based security for OEKE instantiated with an ideal cipher remain open directions.The established OEKE game-based result is stand-alone, whereas BPR security includes man-in-the-middle attackers in the fully concurrent setting.Source: §2.6 · p. 11

3.1 Quantum information

This section introduces quantum-information tools used in the paper, including measurement and quantum rewinding techniques. It also presents a generalization to multiple computations and oracle-simulation results.

Quantum information lemmas

  • The section states the Gentle Measurement lemma and introduces the Hilbert-Schmidt Cauchy-Schwarz inequality as quantum-information tools.It also defines quantum states as trace-one positive semidefinite operators and describes pure states using state vectors and density operators.Source: §3.1 · p. 11

Quantum rewinding

  • A quantum rewinding statement relates the success probabilities of two computations on the same state to sequentially obtaining both outputs with noticeable probability.The paper generalizes this result to n computations selected according to a distribution D.Source: §3.1 · pp. 11–12

Measure-and-reprogram

  • Measure-and-reprogram measures randomly selected oracle-query inputs and reprograms their outputs to support a simulated run.The technique is described for multiple queries, with a staged simulator that receives replacement values as it proceeds.Source: §3.1 · p. 13

Quantum random oracle simulation with extraction

  • The section describes an oracle simulator with separate random-oracle and extraction interfaces, including indistinguishability when extraction is unused.It also states that independent queries to the interfaces almost commute, with error 2/|Y|.Source: §3.1 · p. 13

3.2 KEM

This section defines key encapsulation mechanisms and the post-quantum security notions used in the paper. It specifies correctness and several security properties for KEMs.

KEM algorithms

  • A KEM consists of key generation, encapsulation, and decapsulation algorithms that produce a key pair, a ciphertext with an output key, and a decapsulated key.Key generation may be written with explicit randomness; encapsulation takes a public key, while decapsulation takes a secret key and ciphertext.Source: §3.2 · pp. 13–14

Correctness

  • KEM correctness is defined by a correctness error, and the KEM is correct when that error is negligible.The section also notes that the security parameter is sometimes left implicit.Source: §3.2 · p. 14

Security notions

  • The section defines post-quantum public-key uniformity, key unpredictability, and key indistinguishability against quantum polynomial-time adversaries.It describes the public-key uniformity experiment and gives advantage definitions for the security games.Source: §3.2 · pp. 14–15

3.3 Masny-Rindal OT

This section specifies Masny-Rindal OT from a KEM and defines game-based and simulation-based security notions. It also records the classical UC-security result under stated KEM assumptions.

3.3.1 Syntax

  • Masny-Rindal OT compiles a KEM into random-oracle-model oblivious transfer using two receiver messages, two encapsulations, and decapsulation for the selected choice.The receiver derives two public keys from its transmitted values and random-oracle outputs; the sender encapsulates to both keys.Source: §3.3.1 · p. 15

3.3.2 Game-based security

  • The section defines correctness and security against malicious receivers and senders for two-message OT.It frames the game-based notions for quantum polynomial-time adversaries.Source: §3.3.2 · p. 16

3.3.3 Simulation-based security

  • The simulation-based definition compares interaction with an adversary and honest sender against interaction with a simulator and ideal OT functionality.The paper states that Masny-Rindal OT is classically UC-secure under negligible KEM correctness error, computational public-key uniformity, and key indistinguishability.Source: §3.3.3 · pp. 16–17

3.4 OEKE

This section specifies OEKE as a two-message PAKE template built from a KEM and auxiliary functions, and sets out game-based and UC security frameworks. It describes the PAKE functionality and its session rules.

3.4.1 Syntax

  • OEKE is a two-message PAKE template combining a KEM with password-based encryption and decryption, key derivation, and a tag function.The protocol encapsulates to a public key and derives a session key; the respondent checks a tag before outputting a key or ⊥.Source: §3.4.1 · p. 17

3.4.2 Game-based security

  • The section defines correctness, passive security, and security against malicious initiators and respondents for two-message PAKE.The malicious-party notions use password distributions with min-entropy γ.Source: §3.4.2 · p. 18

3.4.3 UC security

  • The quantum UC framework permits quantum simulators, adversaries, and ideal functionalities while keeping honest parties and the realized functionality classical.The PAKE functionality incorporates one-sided explicit authentication, and the simulator may test a fresh session password only once; NewKey completes the session.Source: §3.4.3 · pp. 18–20
  • The section notes that efficient quantum simulation of an ideal cipher is unresolved, but its (O)EKE UC-insecurity result holds even assuming such a functionality exists.It also identifies Zhandry’s compressed standard oracle as an efficient, perfectly correct simulation of quantum access to a random oracle.Source: §3.4.3 · p. 19

4 Attacks on simulation-based security

Section 4 proves that Masny-Rindal OT is not post-quantum simulation-secure and that OEKE with an ideal cipher does not post-quantum UC-realize the PAKE functionality. The proofs distinguish real and ideal executions despite the stated KEM conditions.

4.1 Masny-Rindal OT

  • Masny-Rindal OT with any KEM having negligible correctness error is not post-quantum simulation-secure.Source: §4.1 · p. 20
  • Without computational public-key uniformity, the OT protocol already fails malicious-sender security.The sender can distinguish the honest receiver’s public key from the uniformly distributed key in the other branch and use that to predict the receiver’s bit.Source: §4.1 · p. 20
  • pReal is 1−negl(λ), whereas pIdeal is at most 3/4+negl(λ) against any simulator.The bound follows from a hybrid in which, in branch c = 1, the measured bit is uniform and independent of the simulator’s choice bit.Source: §4.1 · p. 22

4.2 OEKE with ideal cipher

  • OEKE with ideal-cipher encryption and decryption does not post-quantum UC-realize the PAKE functionality under the theorem’s stated KEM, KDF, and tag conditions.Source: §4.2 · p. 22
  • The OEKE proof assumes computationally uniform public keys; without that property, the protocol fails security against a malicious respondent.Source: §4.2 · p. 23
  • In the ideal-world hybrid, a wrong password guess makes the PAKE key uniform and independent, so matching the real key is negligible.The hybrid instead accepts immediately when the simulator’s password guess matches the tested password.Source: §4.2 · p. 24

5 Provable game-based security

This section establishes post-quantum game-based security for Masny–Rindal OT and, under specific KEM and random-oracle assumptions, 2-Feistel OEKE. Its proofs reduce malicious-adversary attacks to KEM security properties and use indistinguishability and extractable QROM simulation to analyze OEKE security.

5.1 Masny-Rindal OT

  • Masny-Rindal OT satisfies correctness and post-quantum game-based security against malicious receivers and senders when its KEM has negligible correctness error, computationally uniform public keys, and key unpredictability.Source: §5.1 · p. 26
  • A malicious-receiver advantage ε yields at least ε^2 success in the two-output guessing game, which the proof reduces to breaking KEM key unpredictability.The reduction uses measure-and-reprogram and public-key uniformity.Source: §5.1 · pp. 26–27
  • A malicious sender with success 1/2 + ε gives a reduction distinguishing uniform from honestly generated public keys with advantage ε/2.Source: §5.1 · p. 27

5.2 OEKE with 2-Feistel

  • With a correct, UNP-secure KEM with computationally uniform public keys, 2-Feistel encryption, and λ-bit salted key and tag random oracles, OEKE satisfies correctness, passive security, and both malicious-party security notions.Passive security follows from KEM key unpredictability and one-way-to-hiding.Source: §5.2 · p. 28
  • For malicious initiators, the two-output proof bounds the specified reprogramming-order event by 2^-ℓ and establishes search-security success at most 2^-γ + negl.The proof extends to adversaries given derived keys and tags with quantum access to their random oracles.Source: §5.2 · pp. 28–30
  • A two-output adversary succeeds with probability at least ε^3, and the proof’s negligible bound on that game implies ε is negligible.The reduction applies the same strategy to both sampled passwords and outputs both recovered keys.Source: §5.2 · pp. 30–31
  • A malicious initiator wins the full indistinguishability game with probability at most 1/2 + 2^-γ/2 + negl, using salted Hkey reprogramming.The reprogramming yields a hybrid where Hkey(w, *) is independent of K and the adversary’s state after its first message.Source: §5.2 · p. 31
  • The 2-Feistel map makes ϕ uniform and independent of the password, even for an adversary seeing the full H1 and H2 truth tables.This supports a reduction from password guessing to breaking public-key uniformity.Source: §5.2 · p. 31
  • For malicious respondents, acceptance probability above 2^-γ yields a password guess with probability at least 2^-γ + ε − negl, contradicting the password-guessing bound.The proof simulates Htag with an extractable QROM simulator and extracts a password guess from the respondent’s tag.Source: §5.2 · pp. 31–32

6 Advantage-tight one-way to hiding

This section proves a quantum-ROM search-to-decision reduction: a search upper bound transfers to a distinguishing upper bound without loss in advantage, at the cost of potentially greater running time. The proof uses quantum rewinding to amplify the input components responsible for an adversary’s distinguishing advantage.

Search-to-decision reduction

  • If every QPT search algorithm succeeds with probability at most ε(λ) plus negligible error, then every QPT distinguisher’s advantage is also at most ε(λ) plus negligible error.The reduction allows polynomially greater running time; oracle operations are treated as unit cost.Source: §6 · pp. 32–33

Advantage decomposition

  • The distinguishing advantage decomposes into forward and reverse branches that track amplitudes on the target set across the adversary’s oracle queries.The reverse branch starts from the adversary’s final state and runs its computation backward.Source: §6 · pp. 33, 35

Quantum rewinding

  • Coherently running both branches across query positions lets quantum rewinding shift the query-count factor from the advantage bound to the search algorithm’s running time.Alternating input and success projectors amplifies the input components responsible for distinguishing into the success subspace.Source: §6 · p. 33

Singular-value cutoff

  • A singular-value cutoff isolates the input subspace carrying the distinguishing advantage, with the discarded contribution bounded by an error that scales as q/r.The proof then applies amplitude amplification to the retained component.Source: §6 · pp. 34, 36, 37

One-way to hiding

  • The reduction also yields a one-way-to-hiding corollary for a random oracle whose output space has size λ^ω(1), transferring the stated search bound to distinguishing.The proof uses the collision-resistance of the random function in this setting.Source: §6 · pp. 37–38

A Generalizing the attack

The attack extends beyond the specific ideal-cipher OEKE example to known EKE and OEKE variants. For 2-Feistel-based OEKE, the proof uses reversible first-message computation and establishes insecurity under stated KEM and protocol conditions.

EKE

  • The attack also applies to EKE because it needs only the environment’s first message; EKE’s second message additionally encrypts the KEM ciphertext under the password.For EKE, the attack queries D2 to obtain that ciphertext for key derivation.Source: A Generalizing the attack · p. 42

2-Feistel and Tempo

  • The 2-Feistel variant encrypts a public key using random-oracle-derived values and recovers both the public key and randomness during decryption.The paper describes it as more efficient than an ideal cipher but partially malleable: a chosen Δ transforms an encryption of pk into one of pk ⊙ Δ.Source: A Generalizing the attack · p. 42

Attack generalization

  • OEKE instantiated with a negligible-error-correctness KEM, 2-Feistel encryption or Tempo algorithms, any KDF, and any tag function does not post-quantum UC-realize FPAKE-ea.The attack is also stated to apply to all known EKE and OEKE variants.Source: A Generalizing the attack · pp. 42–43

Attack mechanism

  • Given a candidate password, decrypting the first message recovers both the public key and encryption randomness, making the first-message computation classically reversible.This lets the attack reconstruct the post-measurement state used in its test.Source: A Generalizing the attack · p. 43

Tempo

  • The Tempo attack relies on public-key uniformity: when ζ is uniform, its generated key representation must be indistinguishable from a uniform element of PK1.The text identifies UNI-PK+ as an assumption that implies this condition and relates it to Tempo’s post-quantum security.Source: A Generalizing the attack · p. 44

B Modified Measure-and-Reprogram

This appendix adapts measure-and-reprogram lemmas to projectors that can access the reprogrammed random oracle. It states a single-query lemma and an inductively obtained multi-query extension.

Single-query lemma

  • The single-query lemma applies to any fixed function H, input x, output Θ, and projector Πx,Θ, with expectation over the measure-and-reprogram simulator’s choice.The passage notes that the same statement applies when the projector is given access to the reprogrammed oracle.Source: B Modified Measure-and-Reprogram · pp. 44–45

Multi-query lemma

Oracle access

  • The projector must access the reprogrammed H, so it and the adversary evaluate the same oracle after reprogramming.Applying the projector after reprogramming is the stated reason for this choice.Source: B Modified Measure-and-Reprogram · p. 45
Loading 2609.39844v1…