Post-Quantum Security of Block Cipher Constructions

Chen Bai; Christian Majenz; Gorjan Alagic; Kaiyan Shi

arxiv: 2510.08725 · v2 · submitted 2025-10-09 · 💻 cs.CR

Post-Quantum Security of Block Cipher Constructions

Gorjan Alagic , Chen Bai , Christian Majenz , Kaiyan Shi This is my paper

Pith reviewed 2026-05-18 08:26 UTC · model grok-4.3

classification 💻 cs.CR

keywords post-quantum securityblock cipherssymmetric-key cryptographysecurity proofsFX constructionLRWXEXideal cipher model

0 comments

The pith

New techniques deliver the first post-quantum security proofs for FX, LRW, XEX, and standard block cipher modes.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper develops foundations for post-quantum security of block ciphers and the constructions built from them. It shows that the FX key-length extension, the LRW and XEX tweakable block ciphers, and most common encryption and authentication modes remain secure when the adversary has quantum power. A sympathetic reader would care because block ciphers protect internet traffic and stored data today, yet their resistance to quantum computers had not been rigorously established. The proofs apply in both the plain model and the quantum ideal-cipher model.

Core claim

Leveraging new techniques, the first post-quantum security proofs are provided for the key-length extension scheme FX, the tweakable block ciphers LRW and XEX, and most block cipher encryption and authentication modes. The techniques support security proofs in both the plain model and the quantum ideal cipher model, taking initial steps toward a rigorous understanding of the post-quantum security of practical symmetric-key cryptography.

What carries the argument

Quantum security reductions that bound the advantage of a quantum adversary when the underlying block cipher is modeled either as an ideal cipher or under standard assumptions.

If this is right

Quantum adversaries cannot efficiently break these constructions under the stated modeling assumptions.
Encryption and authentication modes inherit post-quantum security directly from the analyzed block-cipher constructions.
Key-length extension via FX yields provable security against quantum attacks when longer keys are used.
The same reduction techniques apply to additional modes not explicitly listed in the proofs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Existing deployed block-cipher implementations may already satisfy post-quantum security if the modeling assumptions match reality.
Similar reduction methods could be applied to other symmetric primitives such as hash functions or message authentication codes.
Concrete security bounds from the proofs could guide the selection of key lengths for quantum-vulnerable deployments.

Load-bearing premise

The security reductions rely on modeling the underlying block cipher either as an ideal cipher in the quantum setting or under standard assumptions in the plain model.

What would settle it

A concrete quantum algorithm that breaks FX, LRW, XEX, or a standard mode with advantage exceeding the proven bound would falsify the results.

read the original abstract

Block ciphers are versatile cryptographic ingredients that are used in a wide range of applications ranging from secure Internet communications to disk encryption. While post-quantum security of public-key cryptography has received significant attention, the case of symmetric-key cryptography (and block ciphers in particular) remains a largely unexplored topic. In this work, we set the foundations for a theory of post-quantum security for block ciphers and associated constructions. Leveraging our new techniques, we provide the first post-quantum security proofs for the key-length extension scheme FX, the tweakable block ciphers LRW and XEX, and most block cipher encryption and authentication modes. Our techniques can be used for security proofs in both the plain model and the quantum ideal cipher model. Our work takes significant initial steps in establishing a rigorous understanding of the post-quantum security of practical symmetric-key cryptography.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

This paper gives the first post-quantum proofs for FX, LRW, XEX and common modes, but the reductions rest on quantum ideal-cipher or plain-model assumptions whose fit to real ciphers is not independently checked.

read the letter

The main thing here is that the authors supply the first post-quantum security proofs for the FX construction, the tweakable ciphers LRW and XEX, and most block-cipher encryption and authentication modes. They do this with new techniques that work in both the plain model and the quantum ideal-cipher model. That fills a clear gap, since almost all prior post-quantum effort has gone into public-key primitives while these symmetric pieces are used constantly in TLS, disk encryption, and authenticated encryption schemes. Giving any rigorous quantum-query bounds for them is a concrete step forward even if the bounds are not yet tight. The paper is straightforward about what it achieves and where it stops. It states the modeling choices up front and does not overclaim applicability to concrete ciphers outside those models. That honesty is useful. The soft spots are exactly where the stress-test note points. The load-bearing step is the choice of model: if a real block cipher admits a quantum superposition attack that violates the ideal-cipher hypothesis or the standard-model assumption used in the reduction, the stated bounds simply do not apply. The abstract gives no query-complexity numbers or error-term details, so it is impossible to judge tightness or hidden looseness without the full derivations. No machine-checked proof or independent lower bound is mentioned to close that gap. These are real but not fatal limitations for a first paper in the area. This work is aimed at researchers who need post-quantum guarantees for symmetric building blocks or who want to extend quantum-query techniques to other modes. A reader already working on quantum symmetric cryptography will find the specific results and the new proof methods worth reading. The paper shows clear thinking and honest engagement with the literature by identifying the unexplored territory and attempting to address it directly. I would bring it to a reading group to discuss the modeling assumptions and the concrete bounds once the full text is available. It deserves a serious referee because the topic matters and the claims are new enough to justify review time, even if revisions on the assumption discussion and bound tightness are likely.

Referee Report

1 major / 2 minor

Summary. The paper introduces new techniques for post-quantum security analysis of block ciphers and associated constructions. It claims to deliver the first post-quantum security proofs for the FX key-length extension scheme, the LRW and XEX tweakable block ciphers, and most standard block-cipher-based encryption and authentication modes. The proofs are developed in both the plain model under standard assumptions and the quantum ideal-cipher model.

Significance. If the reductions hold, the work is significant: it supplies the first rigorous post-quantum bounds for several widely deployed symmetric constructions whose security against quantum adversaries had remained open. The explicit treatment of both plain-model and quantum-ideal-cipher settings, together with the new proof techniques, provides a concrete foundation for future analyses of symmetric-key primitives in the post-quantum regime.

major comments (1)

The load-bearing modeling choice—ideal cipher in the quantum setting versus standard assumptions in the plain model—is stated clearly in the abstract and introduction, but the manuscript does not supply an independent justification or quantum-query lower bound showing that these models adequately capture superposition attacks on concrete block ciphers. Because the concrete security bounds are only meaningful inside the chosen model, a short discussion of the modeling gap (or a reference to existing quantum ideal-cipher literature) would strengthen applicability claims.

minor comments (2)

Notation for quantum query complexity and error terms should be introduced once in a dedicated preliminary section rather than inline in each proof.
Several mode diagrams (e.g., for LRW and XEX) would benefit from explicit indication of which registers are in superposition.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the positive evaluation and the recommendation for minor revision. We address the single major comment below and will revise the manuscript accordingly.

read point-by-point responses

Referee: The load-bearing modeling choice—ideal cipher in the quantum setting versus standard assumptions in the plain model—is stated clearly in the abstract and introduction, but the manuscript does not supply an independent justification or quantum-query lower bound showing that these models adequately capture superposition attacks on concrete block ciphers. Because the concrete security bounds are only meaningful inside the chosen model, a short discussion of the modeling gap (or a reference to existing quantum ideal-cipher literature) would strengthen applicability claims.

Authors: We agree that explicitly addressing the modeling assumptions would strengthen the paper. In the revised manuscript we will insert a concise paragraph (likely in Section 1 or a new short subsection) that motivates the choice of the plain model under standard assumptions for one set of results and the quantum ideal-cipher model for the other. The paragraph will reference the existing literature on the quantum ideal-cipher model (e.g., the foundational works establishing its use for symmetric primitives under superposition queries) and will briefly discuss the modeling gap without claiming that either model fully captures every possible attack on a concrete block cipher. We do not provide a new quantum-query lower bound, as that lies outside the scope of the current work. revision: yes

Circularity Check

0 steps flagged

No circularity: security proofs are independent mathematical reductions in standard models.

full rationale

The paper establishes new post-quantum security proofs for constructions including FX, LRW, XEX and block cipher modes, using techniques applicable in the quantum ideal-cipher model or plain model. These are formal reductions and proofs rather than parameter fits, self-definitions, or renamings of prior results. No equations or steps in the abstract or description reduce any claimed bound to quantities defined by the authors' own inputs or prior self-citations in a load-bearing way. The modeling assumptions are stated explicitly as external choices whose validity is separate from the derivation chain itself, leaving the central proofs self-contained against cryptographic benchmarks.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on standard cryptographic modeling assumptions rather than new free parameters or invented entities. The quantum ideal-cipher model is invoked as a domain assumption for one set of proofs.

axioms (1)

domain assumption Quantum ideal cipher model for the underlying block cipher
Explicitly referenced in the abstract as one of the two settings in which the new techniques apply.

pith-pipeline@v0.9.0 · 5672 in / 1320 out tokens · 48940 ms · 2026-05-18T08:26:50.588289+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

We give a general resampling lemma... for the ideal cipher model... AdvFX_A ≤ 4(q_C √q_Q + q_Q √q_C)·2^−(m+n)/2
IndisputableMonolith/Foundation/RealityFromDistinction.lean reality_from_one_distinction unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

Theorem 7 (informal). ... AdvExp-PQ_Con[E](q,t) ≤ AdvSPRP-PQ_E(q′,t) + δ(q)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

51 extracted references · 51 canonical work pages

[1]

RegisterZis untouched untilD 0 has made all itsqqueries

At the beginning,D 0 sets a specific part of the offline registerE, which we refer to as registerZ, to be|0⟩ Z. RegisterZis untouched untilD 0 has made all itsqqueries

work page
[2]

After makingqquantum queries,D 0 applies a unitary to all its internal registers, includingZ

work page
[3]

We denote the projector|D⟩⟨D| Z asP D

Then, it measures registerZto obtain the distributionD. We denote the projector|D⟩⟨D| Z asP D. Let|ψ 0⟩=|ψ ′ 0⟩KXY E |ϕ0⟩F be the initial state ofD 0. Let |ψ⟩be the quantum state right before the measurement to choose the distributionD. Then, |ψ⟩=U qOq · · ·U 1O1 |ψ0⟩,(29) holds, where eachO i (which is eitherO KXY F orO inv KXY F ) is the unitary operato...

work page
[4]

For eachD, obtaining the (pure) state |ξ0⟩:= X D∈S (k0,s0,s1)∼D p D(k0, s0, s1)P D |ψ⟩KXY EF ⊗ |k0, s0, s1⟩C

Without measuring registerZ(on which the information ofDis written), create the superposition ofk 0,s 0 ands 1 of the form X (k0,s0,s1)∼D p D(k0, s0, s1)|D⟩ Z |k0, s0, s1⟩C . For eachD, obtaining the (pure) state |ξ0⟩:= X D∈S (k0,s0,s1)∼D p D(k0, s0, s1)P D |ψ⟩KXY EF ⊗ |k0, s0, s1⟩C

work page
[5]

Similarly, the stateρ 1 can be produced by measuring the registersZandCof the pure state |ξ1⟩:= X D∈S (k0,s0,s1)∼D p D(k0, s0, s1)Swap Fk0 ,s0 ,Fk0 ,s1 PD |ψ⟩KXY EF ⊗ |k0, s0, s1⟩C

Measure registersZandCto obtain the classical information ofD, k 0, s0, s1. Similarly, the stateρ 1 can be produced by measuring the registersZandCof the pure state |ξ1⟩:= X D∈S (k0,s0,s1)∼D p D(k0, s0, s1)Swap Fk0 ,s0 ,Fk0 ,s1 PD |ψ⟩KXY EF ⊗ |k0, s0, s1⟩C . Since measurements decrease the trace distance between two states, and the trace distance between ...

work page
[6]

Let Tj be the list of the classical queries so far

RunA, answering its classical queries usingRand its quantum queries usingE, untilAmakes its (j+ 1) st classical queryy j+1, which we assume for concreteness to be in the inverse direction. Let Tj be the list of the classical queries so far

work page
[7]

Choose uniforms∈S, and define (E (1))−1 as (E(1) k∗ )−1(y) = ( E−1 k∗ (y) ifk ∗ ̸=k 0 E−1 k0 ◦swap yj+1 ⊕k2, s (y) ifk ∗ =k 0

Define setS={0,1} n\{y1 ⊕k 2,· · ·, y j ⊕k 2}. Choose uniforms∈S, and define (E (1))−1 as (E(1) k∗ )−1(y) = ( E−1 k∗ (y) ifk ∗ ̸=k 0 E−1 k0 ◦swap yj+1 ⊕k2, s (y) ifk ∗ =k 0. Then (E(1) k∗ )(x) = ( Ek∗(x) ifk ∗ ̸=k 0 Ek0 ◦swap E−1 k0 (yj+1 ⊕k2), E−1 k0 (s) (x) ifk ∗ =k 0. Continue runningA, answering its remaining classical queries (including the (j+ 1) st...

work page
[8]

LetT j be the list of classical queries so far

RunA, answering its classical queries usingRand its quantum queries usingE, untilAmakes its (j+ 1) st classical queryy j+1. LetT j be the list of classical queries so far. 38

work page
[9]

Denote the response asx j+1, i.e., xj+1 = (FXK[(E(1))j])−1(yj+1)

DefineE (1) as inH 1,inv j and answer the (j+ 1) st classical query usingFX K[(E(1))Tj ,K]. Denote the response asx j+1, i.e., xj+1 = (FXK[(E(1))j])−1(yj+1). Then the challenger constructsE j+1 adaptively as in Equation 22. Continue runningA, answering its remaining classical queries usingFX K[ETj+1 ,K], and its quantum queries usingE Tj+1 ,K. Next, we pr...

work page
[11]

Query eOwith (m, τ) for 2 n/2 distinct values ofm, obtaining pairs (m, c), wherecis the response, and store them

work page
[12]

Randomly chooseτ ′ ∈ {0,1} n

work page
[13]

Query eOwith (m ′, τ ′) for 2 n/2 distinct values ofm ′, obtaining pairs (m ′, c′), wherec ′ is the response, and store them

work page
[14]

Find a pair (c, c ′) such thatm⊕c=m ′ ⊕c ′

work page
[15]

Example.Consider theLRWconstruction as established in [P1606], whereh k′(τ) =k ′ ×∗ τ

Based on the construction ofh, use the identified pair (c, c ′) (or multiple such pairs) to distinguish between anideal tweakable cipherandLRW. Example.Consider theLRWconstruction as established in [P1606], whereh k′(τ) =k ′ ×∗ τ. For this construction, the attack proceeds as follows:

work page
[16]

Perform steps 1–5 twice to obtain two pairs (c 1, c′

work page
[17]

corresponding to two pairs of tweaks (τ1, τ ′

work page
[18]

Computek ′ 1 = (c1 ⊕c ′ 1)× ∗ (τ1 ⊕τ ′ 1)−1 and similarlyk ′ 2 = (c2 ⊕c ′ 2)× ∗ (τ2 ⊕τ ′ 2)−1

work page
[19]

Otherwise outputideal tweakable cipher

Ifk ′ 1 =k ′ 2, outputLRW. Otherwise outputideal tweakable cipher. Analysis of the Algorithm.If eOisLRW, i.e. eO=LRW k,k′, we defineH k′(m, τ) :=m⊕h k′(τ). Sincehis a universal hash function, for allm, τwith a uniformly selectedk ′,H k′(m, τ) is uniformly distributed. Now, recall that a birthday attack can be applied toH k′. Specifically, with 2n/2 random...

work page
[20]

and (i, j2, i, j′ 2), obtaining the corresponding ciphertext pairs (c 1, c′

work page
[21]

Using these, we compute (c 1 ⊕c ′ 1)× ∗ (αj1 ⊕α j′ 1)−1 and (c2 ⊕c ′ 2)× ∗ (αj2 ⊕α j′ 2)−1 and check whether they match

and (c2, c′ 2). Using these, we compute (c 1 ⊕c ′ 1)× ∗ (αj1 ⊕α j′ 1)−1 and (c2 ⊕c ′ 2)× ∗ (αj2 ⊕α j′ 2)−1 and check whether they match. It they do, this value is the candidate forE k′(2i). Similar arguements work forXEX2. Even-Mansour AttackHere, we use the fact thatLRWwith one tweak is anEven-Mansourto construct the distinguishing attack:

work page
[22]

Randomly choose two tweakst, τ ′ ∈ {0,1} n, and define two oracles P(·) := eO(·, τ), R(·) := eO(·, τ ′)

work page
[23]

Queryf(·) 2 n/2 times and find a collision, i.e.,f(x) =f(x ′)

Definef(x) =P(x)⊕R(x). Queryf(·) 2 n/2 times and find a collision, i.e.,f(x) =f(x ′)

work page
[24]

ComputeR(x ∗ ⊕ek)⊕ ekandP(x ∗)

Randomly selectx ∗ ∈ {0,1} n. ComputeR(x ∗ ⊕ek)⊕ ekandP(x ∗)

work page
[25]

Analysis of the Algorithm.If eOisLRW, i.e

If the two results are equal, outputLRW; otherwise, outputideal tweakable cipher. Analysis of the Algorithm.If eOisLRW, i.e. eO=LRW k,k′, then P(x) = eO(x, τ) =E k(x⊕h k′(τ))⊕h k′(τ) R(x) = eO(x,eτ) =Ek(x⊕h k′(eτ))⊕hk′(eτ). We can rewriteP(x) as follows: P(x) =E k(x⊕h k′(τ)⊕h k′(eτ)⊕h k′(eτ))⊕hk′(τ)⊕h k′(eτ)⊕h k′(eτ) =E k(x⊕ ek⊕h k′(eτ))⊕ek⊕h k′(eτ) =R(x⊕...

work page
[26]

Randomly selectτ∈ {0,1} n

work page
[27]

Use the classical distinguishing attack described above to recoverk ′ (assuming an appropriate hash function construction)

work page
[28]

Construct an oracleE k(·) such that, for an inputx, it replies Ek(x) =LRW k,k′(x⊕h k′(τ), τ)⊕h k′(τ)

work page
[29]

Analysis of the Algorithm.If the tweakable block cipher under investigation is standardizedLRW, then in step 2,k ′ can be computed directly

Perform an exhaustive search to get keyk. Analysis of the Algorithm.If the tweakable block cipher under investigation is standardizedLRW, then in step 2,k ′ can be computed directly. We then perform an exhaustive search to recoverk. Specifically, we first queryLRWusing a constant number of inputs, such as (x⊕h k′(τ), τ). Then, for each candidatek, we quer...

work page
[30]

Randomly chooseτ∈ {0,1} n

work page
[31]

RunAlg-ExpQ1on the definedFandgto recoverkandh (2) k′ (τ)

work page
[32]

UseSimQ1onf k∥h(2) k′ (τ) to recoverh (1) k′ (τ)

work page
[33]

If the check fails, repeat steps 2–4

(Verification) Check ifE(k, k ′)(0n, τ)⊕E k(hk′(τ)) =h k′(τ). If the check fails, repeat steps 2–4

work page
[34]

Based on construction of hash functionh, computek ′. 43 Analysis of the Algorithm.Similar to the classical case, if the tweakable block cipher under in- vestigation is standardizedLRW,k ′ can be easily computed fromh k′(τ) usingk ′ =h k′(τ)× ∗ t−1. So eO(2(n+m)/3) queries (withm≤2n) are required for a complete key search, same as the query complexity of t...

work page
[35]

Selectτ∈ {0,1} n at random

work page
[36]

, s) from{0,1} n at random, ensuringx i ̸=x j fori̸=jand xi /∈ {xi |i= 1,2,

Choosex i (i= 1, . . . , s) from{0,1} n at random, ensuringx i ̸=x j fori̸=jand xi /∈ {xi |i= 1,2, . . . , s}for anyi

work page
[37]

, s, compute di =LRW k,k′(τ, xi)⊕LRW k,k′(τ, xi) by queryingLRW k,k′(·,·) classically

Fori= 1,2, . . . , s, compute di =LRW k,k′(τ, xi)⊕LRW k,k′(τ, xi) by queryingLRW k,k′(·,·) classically. Then define a set D={d i|i= 1,2, . . . , s}. Assume all elements inDare distinct for simplicity

work page
[38]

Create a tableScontaining pairs (d i, xi), sorted byd i

work page
[39]

Findzsuch thatL D(z) = 1 using the Grover algorithm with the unitary operatorV LD, where LD :{0,1} n → {0,1}is defined as LD(x) = ( 0 ifE(k, x)⊕E(k,¯x)/∈D 1 ifE(k, x)⊕E(k,¯x)∈D, , and VLD |x⟩= (−1) LD(x)|x⟩

work page
[40]

Compute d=E(k, z)⊕E(k,¯z), then find anxfrom tableSsuch that d=LRW k,k′(τ, x)⊕LRW k,k′(τ,¯x)

work page
[41]

Selectx ′ ∈ {0,1} n at random and obtainLRW k,k′(τ, x′) by queryingLRW k,k′(·,·) classically

work page
[42]

IfE(k, x ′)⊕h k′(τ)̸=LRW k,k′(τ, x′), then seth k′ = ¯x⊕z

work page
[43]

If hk′(τ1), hk′(τ2), hk′(τ3) are not uniformly distributed, output 1; otherwise, output 0

Repeat step 2–10 three times to obtain three pairs: (τ 1, hk′(τ1)), (τ 2, hk′(τ2)), and (τ 3, hk′(τ3)). If hk′(τ1), hk′(τ2), hk′(τ3) are not uniformly distributed, output 1; otherwise, output 0

work page
[44]

Treat steps 2–11 as a predicatef, wheref(k)∈ {0,1}, and findksuch thatf(k) = 1 using the Grover algorithm with the unitary operatorU f

work page
[45]

modified cipher

(Verification) If a validkis found, computek ′ based on the construction of the hash functionh and output 1 or 0 accordingly. Analysis of the Algorithm.This combined attack employs BHT to recover the tweak termh k′(τ) and Grover’s algorithm to find the cipher keyk. Therefore, it requiresq Q =O(2 m/2 ·2 n/3) = O(2m/2+n/3) quantum queries andq C =O(2 n/3) c...

work page
[46]

LetT j ={(τ 1, x1, y1),

RunA, answering its classical queries using eΠand its quantum queries usingE, stopping immedi- atelybeforeits (j+1) st classical query. LetT j ={(τ 1, x1, y1), . . . ,(τj, xj, yj)}be the list of classical queries so far

work page
[47]

Experiment H1 j

For the remainder of the execution ofA, answer its classical queries byLRW K[ETj ,K] and its quantum queries byE Tj ,k. Experiment H1 j

work page
[49]

Continue runningA, answering its remaining classical queries (including the (j+ 1) st) using LRWK[(E(1))Tj ,K], and its quantum queries using (E (1))Tj ,K

Choose uniforms∈ {0,1} n, and defineE (1) as E(1) k∗ (x) = ( Ek∗(x) ifk ∗ ̸=k Ek ◦swap xj+1 ⊕hk′ (τj+1 ), s (x) ifk ∗ =k. Continue runningA, answering its remaining classical queries (including the (j+ 1) st) using LRWK[(E(1))Tj ,K], and its quantum queries using (E (1))Tj ,K. Experiment H2 j

work page
[50]

RunA, answering its classical queries using eΠand its quantum queries usingE, untilAmakes its (j+ 1) st classical query (τ j+1, xj+1)

work page
[51]

Denote the response as yj+1, i.e., yj+1 =LRW K[(E(1))j](τj+1, xj+1)

DefineE (1) as inH 1 j and answer the (j+ 1) st usingLRW K[(E(1))Tj ,K]. Denote the response as yj+1, i.e., yj+1 =LRW K[(E(1))j](τj+1, xj+1). Continue runningA, answering its remaining classical queries usingLRW K[ETj+1 ,K], and its quan- tum queries usingE Tj+1 ,K. Experiment H3 j

work page
[52]

LetT j+1 ={(τ 1, x1, y1),

RunA, answering its classical queries using eΠand its quantum queries usingE, stopping imme- diatelyafterits (j+ 1) st classical query. LetT j+1 ={(τ 1, x1, y1), . . . ,(τj+1, xj+1, yj+1)}be the classical queries so far

work page
[53]

We can compactly represent Hj,H 1 j ,H 2 j ,H 3 j ,H j+1 as the experiment in whichA’s queries are answered using the following oracle sequences

For the remainder of the execution ofA, answer its classical queries usingLRW K ETj+1 ,K and its quantum queries usingE Tj+1 ,K, i.e.|E j+1⟩. We can compactly represent Hj,H 1 j ,H 2 j ,H 3 j ,H j+1 as the experiment in whichA’s queries are answered using the following oracle sequences. We also define (E (1))j to denote (E (1) k )Tj ,K. Hj :|E⟩, eΠ,|E⟩,· ...

work page

[1] [1]

RegisterZis untouched untilD 0 has made all itsqqueries

At the beginning,D 0 sets a specific part of the offline registerE, which we refer to as registerZ, to be|0⟩ Z. RegisterZis untouched untilD 0 has made all itsqqueries

work page

[2] [2]

After makingqquantum queries,D 0 applies a unitary to all its internal registers, includingZ

work page

[3] [3]

We denote the projector|D⟩⟨D| Z asP D

Then, it measures registerZto obtain the distributionD. We denote the projector|D⟩⟨D| Z asP D. Let|ψ 0⟩=|ψ ′ 0⟩KXY E |ϕ0⟩F be the initial state ofD 0. Let |ψ⟩be the quantum state right before the measurement to choose the distributionD. Then, |ψ⟩=U qOq · · ·U 1O1 |ψ0⟩,(29) holds, where eachO i (which is eitherO KXY F orO inv KXY F ) is the unitary operato...

work page

[4] [4]

For eachD, obtaining the (pure) state |ξ0⟩:= X D∈S (k0,s0,s1)∼D p D(k0, s0, s1)P D |ψ⟩KXY EF ⊗ |k0, s0, s1⟩C

Without measuring registerZ(on which the information ofDis written), create the superposition ofk 0,s 0 ands 1 of the form X (k0,s0,s1)∼D p D(k0, s0, s1)|D⟩ Z |k0, s0, s1⟩C . For eachD, obtaining the (pure) state |ξ0⟩:= X D∈S (k0,s0,s1)∼D p D(k0, s0, s1)P D |ψ⟩KXY EF ⊗ |k0, s0, s1⟩C

work page

[5] [5]

Similarly, the stateρ 1 can be produced by measuring the registersZandCof the pure state |ξ1⟩:= X D∈S (k0,s0,s1)∼D p D(k0, s0, s1)Swap Fk0 ,s0 ,Fk0 ,s1 PD |ψ⟩KXY EF ⊗ |k0, s0, s1⟩C

Measure registersZandCto obtain the classical information ofD, k 0, s0, s1. Similarly, the stateρ 1 can be produced by measuring the registersZandCof the pure state |ξ1⟩:= X D∈S (k0,s0,s1)∼D p D(k0, s0, s1)Swap Fk0 ,s0 ,Fk0 ,s1 PD |ψ⟩KXY EF ⊗ |k0, s0, s1⟩C . Since measurements decrease the trace distance between two states, and the trace distance between ...

work page

[6] [6]

Let Tj be the list of the classical queries so far

RunA, answering its classical queries usingRand its quantum queries usingE, untilAmakes its (j+ 1) st classical queryy j+1, which we assume for concreteness to be in the inverse direction. Let Tj be the list of the classical queries so far

work page

[7] [7]

Choose uniforms∈S, and define (E (1))−1 as (E(1) k∗ )−1(y) = ( E−1 k∗ (y) ifk ∗ ̸=k 0 E−1 k0 ◦swap yj+1 ⊕k2, s (y) ifk ∗ =k 0

Define setS={0,1} n\{y1 ⊕k 2,· · ·, y j ⊕k 2}. Choose uniforms∈S, and define (E (1))−1 as (E(1) k∗ )−1(y) = ( E−1 k∗ (y) ifk ∗ ̸=k 0 E−1 k0 ◦swap yj+1 ⊕k2, s (y) ifk ∗ =k 0. Then (E(1) k∗ )(x) = ( Ek∗(x) ifk ∗ ̸=k 0 Ek0 ◦swap E−1 k0 (yj+1 ⊕k2), E−1 k0 (s) (x) ifk ∗ =k 0. Continue runningA, answering its remaining classical queries (including the (j+ 1) st...

work page

[8] [8]

LetT j be the list of classical queries so far

RunA, answering its classical queries usingRand its quantum queries usingE, untilAmakes its (j+ 1) st classical queryy j+1. LetT j be the list of classical queries so far. 38

work page

[9] [9]

Denote the response asx j+1, i.e., xj+1 = (FXK[(E(1))j])−1(yj+1)

DefineE (1) as inH 1,inv j and answer the (j+ 1) st classical query usingFX K[(E(1))Tj ,K]. Denote the response asx j+1, i.e., xj+1 = (FXK[(E(1))j])−1(yj+1). Then the challenger constructsE j+1 adaptively as in Equation 22. Continue runningA, answering its remaining classical queries usingFX K[ETj+1 ,K], and its quantum queries usingE Tj+1 ,K. Next, we pr...

work page

[10] [11]

Query eOwith (m, τ) for 2 n/2 distinct values ofm, obtaining pairs (m, c), wherecis the response, and store them

work page

[11] [12]

Randomly chooseτ ′ ∈ {0,1} n

work page

[12] [13]

Query eOwith (m ′, τ ′) for 2 n/2 distinct values ofm ′, obtaining pairs (m ′, c′), wherec ′ is the response, and store them

work page

[13] [14]

Find a pair (c, c ′) such thatm⊕c=m ′ ⊕c ′

work page

[14] [15]

Example.Consider theLRWconstruction as established in [P1606], whereh k′(τ) =k ′ ×∗ τ

Based on the construction ofh, use the identified pair (c, c ′) (or multiple such pairs) to distinguish between anideal tweakable cipherandLRW. Example.Consider theLRWconstruction as established in [P1606], whereh k′(τ) =k ′ ×∗ τ. For this construction, the attack proceeds as follows:

work page

[15] [16]

Perform steps 1–5 twice to obtain two pairs (c 1, c′

work page

[16] [17]

corresponding to two pairs of tweaks (τ1, τ ′

work page

[17] [18]

Computek ′ 1 = (c1 ⊕c ′ 1)× ∗ (τ1 ⊕τ ′ 1)−1 and similarlyk ′ 2 = (c2 ⊕c ′ 2)× ∗ (τ2 ⊕τ ′ 2)−1

work page

[18] [19]

Otherwise outputideal tweakable cipher

Ifk ′ 1 =k ′ 2, outputLRW. Otherwise outputideal tweakable cipher. Analysis of the Algorithm.If eOisLRW, i.e. eO=LRW k,k′, we defineH k′(m, τ) :=m⊕h k′(τ). Sincehis a universal hash function, for allm, τwith a uniformly selectedk ′,H k′(m, τ) is uniformly distributed. Now, recall that a birthday attack can be applied toH k′. Specifically, with 2n/2 random...

work page

[19] [20]

and (i, j2, i, j′ 2), obtaining the corresponding ciphertext pairs (c 1, c′

work page

[20] [21]

Using these, we compute (c 1 ⊕c ′ 1)× ∗ (αj1 ⊕α j′ 1)−1 and (c2 ⊕c ′ 2)× ∗ (αj2 ⊕α j′ 2)−1 and check whether they match

and (c2, c′ 2). Using these, we compute (c 1 ⊕c ′ 1)× ∗ (αj1 ⊕α j′ 1)−1 and (c2 ⊕c ′ 2)× ∗ (αj2 ⊕α j′ 2)−1 and check whether they match. It they do, this value is the candidate forE k′(2i). Similar arguements work forXEX2. Even-Mansour AttackHere, we use the fact thatLRWwith one tweak is anEven-Mansourto construct the distinguishing attack:

work page

[21] [22]

Randomly choose two tweakst, τ ′ ∈ {0,1} n, and define two oracles P(·) := eO(·, τ), R(·) := eO(·, τ ′)

work page

[22] [23]

Queryf(·) 2 n/2 times and find a collision, i.e.,f(x) =f(x ′)

Definef(x) =P(x)⊕R(x). Queryf(·) 2 n/2 times and find a collision, i.e.,f(x) =f(x ′)

work page

[23] [24]

ComputeR(x ∗ ⊕ek)⊕ ekandP(x ∗)

Randomly selectx ∗ ∈ {0,1} n. ComputeR(x ∗ ⊕ek)⊕ ekandP(x ∗)

work page

[24] [25]

Analysis of the Algorithm.If eOisLRW, i.e

If the two results are equal, outputLRW; otherwise, outputideal tweakable cipher. Analysis of the Algorithm.If eOisLRW, i.e. eO=LRW k,k′, then P(x) = eO(x, τ) =E k(x⊕h k′(τ))⊕h k′(τ) R(x) = eO(x,eτ) =Ek(x⊕h k′(eτ))⊕hk′(eτ). We can rewriteP(x) as follows: P(x) =E k(x⊕h k′(τ)⊕h k′(eτ)⊕h k′(eτ))⊕hk′(τ)⊕h k′(eτ)⊕h k′(eτ) =E k(x⊕ ek⊕h k′(eτ))⊕ek⊕h k′(eτ) =R(x⊕...

work page

[25] [26]

Randomly selectτ∈ {0,1} n

work page

[26] [27]

Use the classical distinguishing attack described above to recoverk ′ (assuming an appropriate hash function construction)

work page

[27] [28]

Construct an oracleE k(·) such that, for an inputx, it replies Ek(x) =LRW k,k′(x⊕h k′(τ), τ)⊕h k′(τ)

work page

[28] [29]

Analysis of the Algorithm.If the tweakable block cipher under investigation is standardizedLRW, then in step 2,k ′ can be computed directly

Perform an exhaustive search to get keyk. Analysis of the Algorithm.If the tweakable block cipher under investigation is standardizedLRW, then in step 2,k ′ can be computed directly. We then perform an exhaustive search to recoverk. Specifically, we first queryLRWusing a constant number of inputs, such as (x⊕h k′(τ), τ). Then, for each candidatek, we quer...

work page

[29] [30]

Randomly chooseτ∈ {0,1} n

work page

[30] [31]

RunAlg-ExpQ1on the definedFandgto recoverkandh (2) k′ (τ)

work page

[31] [32]

UseSimQ1onf k∥h(2) k′ (τ) to recoverh (1) k′ (τ)

work page

[32] [33]

If the check fails, repeat steps 2–4

(Verification) Check ifE(k, k ′)(0n, τ)⊕E k(hk′(τ)) =h k′(τ). If the check fails, repeat steps 2–4

work page

[33] [34]

Based on construction of hash functionh, computek ′. 43 Analysis of the Algorithm.Similar to the classical case, if the tweakable block cipher under in- vestigation is standardizedLRW,k ′ can be easily computed fromh k′(τ) usingk ′ =h k′(τ)× ∗ t−1. So eO(2(n+m)/3) queries (withm≤2n) are required for a complete key search, same as the query complexity of t...

work page

[34] [35]

Selectτ∈ {0,1} n at random

work page

[35] [36]

, s) from{0,1} n at random, ensuringx i ̸=x j fori̸=jand xi /∈ {xi |i= 1,2,

Choosex i (i= 1, . . . , s) from{0,1} n at random, ensuringx i ̸=x j fori̸=jand xi /∈ {xi |i= 1,2, . . . , s}for anyi

work page

[36] [37]

, s, compute di =LRW k,k′(τ, xi)⊕LRW k,k′(τ, xi) by queryingLRW k,k′(·,·) classically

Fori= 1,2, . . . , s, compute di =LRW k,k′(τ, xi)⊕LRW k,k′(τ, xi) by queryingLRW k,k′(·,·) classically. Then define a set D={d i|i= 1,2, . . . , s}. Assume all elements inDare distinct for simplicity

work page

[37] [38]

Create a tableScontaining pairs (d i, xi), sorted byd i

work page

[38] [39]

Findzsuch thatL D(z) = 1 using the Grover algorithm with the unitary operatorV LD, where LD :{0,1} n → {0,1}is defined as LD(x) = ( 0 ifE(k, x)⊕E(k,¯x)/∈D 1 ifE(k, x)⊕E(k,¯x)∈D, , and VLD |x⟩= (−1) LD(x)|x⟩

work page

[39] [40]

Compute d=E(k, z)⊕E(k,¯z), then find anxfrom tableSsuch that d=LRW k,k′(τ, x)⊕LRW k,k′(τ,¯x)

work page

[40] [41]

Selectx ′ ∈ {0,1} n at random and obtainLRW k,k′(τ, x′) by queryingLRW k,k′(·,·) classically

work page

[41] [42]

IfE(k, x ′)⊕h k′(τ)̸=LRW k,k′(τ, x′), then seth k′ = ¯x⊕z

work page

[42] [43]

If hk′(τ1), hk′(τ2), hk′(τ3) are not uniformly distributed, output 1; otherwise, output 0

Repeat step 2–10 three times to obtain three pairs: (τ 1, hk′(τ1)), (τ 2, hk′(τ2)), and (τ 3, hk′(τ3)). If hk′(τ1), hk′(τ2), hk′(τ3) are not uniformly distributed, output 1; otherwise, output 0

work page

[43] [44]

Treat steps 2–11 as a predicatef, wheref(k)∈ {0,1}, and findksuch thatf(k) = 1 using the Grover algorithm with the unitary operatorU f

work page

[44] [45]

modified cipher

(Verification) If a validkis found, computek ′ based on the construction of the hash functionh and output 1 or 0 accordingly. Analysis of the Algorithm.This combined attack employs BHT to recover the tweak termh k′(τ) and Grover’s algorithm to find the cipher keyk. Therefore, it requiresq Q =O(2 m/2 ·2 n/3) = O(2m/2+n/3) quantum queries andq C =O(2 n/3) c...

work page

[45] [46]

LetT j ={(τ 1, x1, y1),

RunA, answering its classical queries using eΠand its quantum queries usingE, stopping immedi- atelybeforeits (j+1) st classical query. LetT j ={(τ 1, x1, y1), . . . ,(τj, xj, yj)}be the list of classical queries so far

work page

[46] [47]

Experiment H1 j

For the remainder of the execution ofA, answer its classical queries byLRW K[ETj ,K] and its quantum queries byE Tj ,k. Experiment H1 j

work page

[47] [49]

Continue runningA, answering its remaining classical queries (including the (j+ 1) st) using LRWK[(E(1))Tj ,K], and its quantum queries using (E (1))Tj ,K

Choose uniforms∈ {0,1} n, and defineE (1) as E(1) k∗ (x) = ( Ek∗(x) ifk ∗ ̸=k Ek ◦swap xj+1 ⊕hk′ (τj+1 ), s (x) ifk ∗ =k. Continue runningA, answering its remaining classical queries (including the (j+ 1) st) using LRWK[(E(1))Tj ,K], and its quantum queries using (E (1))Tj ,K. Experiment H2 j

work page

[48] [50]

RunA, answering its classical queries using eΠand its quantum queries usingE, untilAmakes its (j+ 1) st classical query (τ j+1, xj+1)

work page

[49] [51]

Denote the response as yj+1, i.e., yj+1 =LRW K[(E(1))j](τj+1, xj+1)

DefineE (1) as inH 1 j and answer the (j+ 1) st usingLRW K[(E(1))Tj ,K]. Denote the response as yj+1, i.e., yj+1 =LRW K[(E(1))j](τj+1, xj+1). Continue runningA, answering its remaining classical queries usingLRW K[ETj+1 ,K], and its quan- tum queries usingE Tj+1 ,K. Experiment H3 j

work page

[50] [52]

LetT j+1 ={(τ 1, x1, y1),

RunA, answering its classical queries using eΠand its quantum queries usingE, stopping imme- diatelyafterits (j+ 1) st classical query. LetT j+1 ={(τ 1, x1, y1), . . . ,(τj+1, xj+1, yj+1)}be the classical queries so far

work page

[51] [53]

We can compactly represent Hj,H 1 j ,H 2 j ,H 3 j ,H j+1 as the experiment in whichA’s queries are answered using the following oracle sequences

For the remainder of the execution ofA, answer its classical queries usingLRW K ETj+1 ,K and its quantum queries usingE Tj+1 ,K, i.e.|E j+1⟩. We can compactly represent Hj,H 1 j ,H 2 j ,H 3 j ,H j+1 as the experiment in whichA’s queries are answered using the following oracle sequences. We also define (E (1))j to denote (E (1) k )Tj ,K. Hj :|E⟩, eΠ,|E⟩,· ...

work page