PaperlayerView exact revision on arXiv

Source-linked AI summary

On The Simplest Quantum-Secure Block Cipher

Gorjan Alagic, Joseph Carolan, Christian Majenz, Saliha Tokat

arXiv:2609.40350v1quant-phcs.CR

TL;DR

Quantum-query security for key-alternating ciphers beyond one round was unclear, despite the framework’s classical security. This paper proves Q2 security for two-round Even–Mansour and gives a generic attack on one-call constructions.

Abstract

from arXiv · show

Pseudorandom permutations are ubiquitous in theoretical and applied cryptography. PRPs that offer security even against adversaries making quantum queries are of increasing interest, and used in applications ranging from constructing pseudorandom unitaries to separating SZK from BQP. A successful framework for constructing classically-secure PRPs is the key-alternating Even-Mansour approach, which interleaves applications of public permutations with additions of round keys. The single-round construction is already classically secure in the ideal permutation model (IPM), with added rounds offering improved concrete security. However, in the quantum-query setting, the status of this framework is presently unclear. A simple quantum-query attack based on Simon's algorithm breaks the one-round cipher. For two or more rounds, security is only known against non-adaptive adversaries who must prepare all queries in advance. In this work, we show that the two-round Even-Mansour cipher is information theoretically secure in the IPM against adversaries making polynomially-many adaptive forward and inverse quantum queries to all available oracles. Our proof uses compressed permutation oracles and a specially crafted isometry relating the ideal and real experiments. We also show that this construction is minimal, in the sense that essentially any cipher constructed via a single call to a public permutation is quantumly insecure.

1 Introduction

The introduction asks whether key alternation can provide quantum-query security beyond the one-round construction, whose Q2 security is vulnerable. It presents two-round Even–Mansour as a Q2-secure PRP and argues that one public-permutation call is insufficient in the stated setting.

1 Introduction

  • For t > 1, Q2 security had been unknown, while prior guarantees covered non-adaptive adversaries; one-round Even–Mansour is vulnerable to Simon’s algorithm.In the classical setting, the one-round construction is secure up to O(2^n/2) queries.Source: §1 · pp. 1–2, §1.1 · p. 2

1.1 Technical summary of results

  • Two-round Even–Mansour is indistinguishable from a random permutation against polynomial-query Q2 adversaries.The construction is a strong qPRP in the ideal permutation model.Source: §1 · p. 2, Two-round Even-Mansour is a qPRP · p. 3
  • A generic polynomial-query quantum attack rules out essentially any one-call public-permutation cipher in the stated scope.The discussion specifies sufficiently large cipher domains and constructions that are permutations of the same size as the public permutation.Source: §1 · p. 2, §1.1 · p. 2, All one-query constructions are insecure · p. 3
  • The one-query result assumes a sufficiently large cipher domain, and the stated technical result requires the constructed cipher to be a permutation, not merely indistinguishable from one.The paper leaves removing the latter limitation to future work.Source: All one-query constructions are insecure · p. 3
  • The proof instantiates random permutations with compressed permutation-oracle databases and connects ideal and real experiments through an isometry and a sequence of hybrids.The isometry translates ideal-permutation query entries into the corresponding inner-permutation database entries before removing the ideal entry.Source: Two-round Even-Mansour is a qPRP · p. 4
  • Good databases make the isometry orthogonality-preserving by restricting its branches to positive coefficients.Their directional structure forces entries to be filled or removed in the appropriate isometry steps.Source: Two-round Even-Mansour is a qPRP · p. 5

2 Preliminaries

The preliminaries establish database and XOR-shift notation, then introduce compressed permutation oracles as a way to represent permutation queries. They also state that conditioning on low-probability events under compression can preserve soundness.

2 Preliminaries

  • [N] denotes the n-bit domain, S ⊕ k shifts a set by key k, and a database is a partial function whose size is its domain size.The notation also distinguishes a database’s domain and image.Source: §2 · p. 5

2.1 Compressed Permutation Oracle

  • A compressed permutation oracle stores an injective partial function in a private database initialized with undefined entries, which can be extended by queried input-output pairs.The database is represented as a truth table with undefined entries marked ⊥.Source: §2.1 · p. 6
  • Under compression, one can condition on a low-probability event not occurring without sacrificing soundness.The text presents this as a general fact for compression of both permutations and functions.Source: §2.1 · p. 6

3 Quantum Security of Two-round Even-Mansour

This section develops the proof of a quantum-query theorem for two-round Even–Mansour using query operators, an ideal-to-real isometry, and hybrid comparisons. It analyzes forward and inverse query differences, including a real-world versus ideal-world comparison in the stated range t≥1 and t²≤N/2.

3 Quantum Security of Two-round Even-Mansour

  • Theorem 3 considers quantum algorithms making at most q forward and inverse queries, in the regime q^2 ≤ N/2.The supplied theorem passage omits the bound itself.Source: §3 · p. 7

3.1 Query operators.

  • Inverse queries are implemented by conjugation with M, which swaps D1 and D2 and reduces their bounds to forward-query bounds plus a commutator bound.Inverse queries to P1 and P2 use the forward operators for P2 and P1, respectively.Source: §3.1 · p. 8

3.2 Setup

  • The ideal-to-real isometry fills related D1 and D2 entries for construction queries recorded in D3, preserving injectivity so the construction query can be recovered.It flips D2 before filling and back afterward, then uncomputes D3 entries whenever possible.Source: Isometry from ideal to real world · pp. 10–11

3.3 Hybrids difference

  • The hybrid difference interleaves ideal queries with Πg and Πinj to avoid loosening the bound, using Π⋆ = ΠgΠinj.Source: §3.3 · p. 12
  • The hybrid-difference analysis identifies the t-th summand as the difference at the t-th query, with Theorem 4 applying when q² ≤ N/2.Source: §3.3 · p. 13

3.4 Reducing inverse queries to forward ones

  • Inverse-query hybrid differences equal forward-query differences for i = 3; for i = 1 and 2, the reduction swaps the index.Source: §3.4 · p. 13

3.5 Bounding the forward query hybrids

  • For forward-query hybrids, query-controlled projectors align real and ideal oracle answers and constrain the isometry; Lemmas 9 and 10 bound violations of the required good-query conditions.Source: §3.5 · p. 14

(2) We get

  • For forward P1 and P2 queries, Theorems 6 and 7 bound the hybrid differences when t ≥ 1 and t² ≤ N/2.The P2 analysis has additional complications because P2 can be pointed to by both D1 and D3.Source: (2) We get · p. 15, P2-query · p. 21
  • For P3 queries, the isometry is split into query-controlled factors, and irrelevant factors are discarded to remove dependence on their order.The passage describes fill and removal on the queried D3 register, with Γ1 and Γ2 enforcing the target-register conditions.Source: P2-query · p. 21
  • Theorem 8 considers a forward query to the real-world construction and to P3 in the ideal world for integers t≥1 satisfying t^2≤N/2.The supplied passage omits the theorem’s conclusion.Source: P2-query · p. 22

A.1 Proof of Corollary 1

The proof fixes a query and partial database, compares two operators on the remaining database register, and uses norm monotonicity to complete the bound.

A.1 Proof of Corollary 1

  • The proof fixes query register X to |x⟩ and the complementary database register to a basis value D′, which is injective and has size at most t.It also defines SD′ as the elements of [N] outside Im(D′).Source: §A.1 · p. 25
  • Conditioned on D′, fC and pC act on Dx as Exc(|⊥⟩, |+n⟩) and Exc(|⊥⟩, |SD′⟩), respectively, with the latter restricted to the injective subspace.Source: §A.1 · p. 25
  • Lemma 3 bounds the difference between these operators, and norm monotonicity plus their preservation of X in the computational basis yields the claim.Source: §A.1 · p. 25

B One Query Impossibility Deferred Proof

The proof combines key-specific tests to separate the real and ideal experiments, while a structural lemma characterizes the bijectivity required of single-permutation keyed functions.

B One Query Impossibility Deferred Proof

C Projector Violation Bound Deferred Proofs

This section collects proofs of the single-query violation bounds for the database projectors.

C Projector Violation Bound Deferred Proofs

C.1 Proof of Lemma 4

The proof shows that a compressed query increases the database-space bound by at most one entry.

C.1 Proof of Lemma 4

  • A query maps states in Π_t H into Π_(t+1) H, because it either preserves the database size or adds one entry.The proof separates the cases where the response is already defined and where it is ⊥.Source: §C.1 · p. 29

C.2 Proof of Lemma 5

These deferred proofs bound projector violations for forward and inverse queries, then address the bounds in Lemmas 9 and 10.

C.2 Proof of Lemma 5

  • Forward and inverse query bounds are handled across database blocks, including coherent superpositions of query types.The proof treats injectivity and goodness projectors, with a separate inverse-query argument for goodness without an injectivity assumption.Source: §C.2 · pp. 29, 31, 32

C.3 Proof of Lemma 9

  • Lemma 9 treats P1, P2, and P3 queries separately when deriving the single-query bounds.The P3 case is stated to follow the P1 argument with Dom(D3) replaced by Dom(D1).Source: §C.3 · pp. 32–33

D Hybrid Differences Deferred Proofs

These deferred proofs develop the hybrid-difference bounds used in the security analysis. They rely on norm inequalities and properties of the query-generated database states.

D Hybrid Differences Deferred Proofs

D.1 Proof of Lemma 6

  • Lemma 6 follows using Lemmas 4 and 5 together with submultiplicativity of the norm.Source: §D.1 · p. 34

D.2 Proof of Theorem 4

  • Theorem 4's bound uses that the evolving query state lies in a projected subspace while the key registers retain uniform superpositions.The first t−1 queries increase each database's size by at most t−1; ideal queries and projectors leave K1 and K3 untouched.Source: §D.2 · p. 35

E Reducing Inverse Queries to Forward Ones Deferred Proofs

These proofs reduce inverse-query analysis to forward queries by showing that the conversion operator M respects the database subspaces and the isometry used in the proof. The resulting theorem proof then applies the forward-query bound.

E.1 Proof of Lemma 7

  • M commutes with database-size and injectivity projectors, and preserves the good-database subspace on injective databases.It also commutes with the projector onto the uniform state of K1 and K3.Source: §E.1 · p. 35

E.2 Proof of Lemma 8

  • The isometry V commutes with M on good databases because its forward- and inverse-database operations are symmetric and preserve the conditions needed for M's flip.The proof treats the flip and removal components separately; V's removal component introduces no new D3 entry on good databases.Source: §E.2 · pp. 36–37

E.3 Proof of Theorem 5

  • The expression is rewritten by Lemma 8; because a single query increases database size by at most 1 (Lemma 4), unitary invariance and submultiplicativity are used on the norm of term (171).Source: §E.3 · p. 37

F P1-query: Deferred Proofs

The deferred proofs establish database-state properties used in the P1- and P2-query bounds. The P2 analysis uses Theorem 5 to focus on forward queries and maintains good-database conditions under specified extensions.

F.1 Proof of Lemma 11

  • For the P1-query proof, the isometry's basis-state images have positive coefficients, and orthogonal inputs yield orthogonal image terms.The argument applies when the database with k2 is good and the relevant fill operation is inactive or acts as the identity.Source: §F.1 · p. 37, G P2-query Bound Deferred Proofs · p. 39

G P2-query Bound Deferred Proofs

G.1 Proof of Theorem 7

The proof bounds operator, commutator, and decompression errors using database-register decompositions, orthogonality, injectivity-preserving operations, and good database restrictions, reducing the deferred P3-query analysis to a forward-query case.

G.1 Proof of Theorem 7

  • On good databases, orthogonality and Lemma 14 support bounding decompression commutator terms with triangle-inequality and Cauchy–Schwarz arguments, including an O(t/N) bound.The proof treats the terms similarly, detailing one and bounding the rest briefly.Source: §G.1 · pp. 41, 45
  • For states preserved by Π⋆, x stays outside Im(D1)⊕k2, so Vrmv never uses D2_x as a control and the commutator difference is zero.The proof says fC’s action on D2_x is therefore irrelevant.Source: §G.1 · p. 47

H P3-query Bound Deferred Proofs

  • Using Theorem 5, the P3-query analysis reduces to forward queries with b = 0 and i = 3, where the isometry fills and removes the queried D3 register.The fill requires both target registers to be ⊥; splitting the isometry by the query register helps remove order dependence.Source: H P3-query Bound Deferred Proofs · p. 47
  • The deferred proof factors cOR as fC(1) · W · fC(1), with W := fC(2) · Pem · fC(2), then reduces the commutator to simpler terms bounded separately.It fixes the query and key registers in the computational basis and uses norm unitarity in the reduction.Source: H P3-query Bound Deferred Proofs · p. 48
  • The first commutator is simplified by replacing W with decompression eW, whose action preserves the relevant set and leaves only injectivity-related differences.The proof uses disjoint registers and injectivity preservation to show the remaining difference vanishes after projecting out flip failures.Source: H P3-query Bound Deferred Proofs · pp. 49–50
  • For [fC(1), Vpc], restricting the database index to exclude x ⊕ k1 preserves goodness, and the resulting fill-set discrepancy is bounded by O(t/N).The conflicting register can make one set differ by a missing element; the remaining difference is bounded as in the earlier P1-query argument.Source: H P3-query Bound Deferred Proofs · p. 50
  • For the commutator involving W, the proof restores D2 injectivity before and after W at O(t/N) cost, then applies the preceding argument.The restricted database remains good through Vp and fC(1), and W is controlled on X and K1.Source: H P3-query Bound Deferred Proofs · pp. 50–51
  • Lemma 17 bounds decompression movement for fixed X, K1, K2 and pairwise-orthogonal Hadamard-basis components, with an O(t/N)-scale bound.The passage also states that the first-term bound still holds when ℓy′ = 0.Source: H P3-query Bound Deferred Proofs · p. 51

H.1 Proof of Theorem 8

The proof relates the ideal and real experiments with an isometry and bounds their hybrid difference. It analyzes the difference through cases classified in the Hadamard basis.

H.1 Proof of Theorem 8

  • Two additional projectors let the isometry transfer the ideal-world query answer from database D3 to D1 and D2.The proof then drops projectors whose conditions are already enforced by Γ1 and Γ2, retaining Πinj.Source: §H.1 · p. 53
  • The Γ2 bound applies even after cOI, so the proof does not pay for that violation at every occurrence.The stated condition is a uniform K3 superposition and a D2 database of size at most t.Source: §H.1 · p. 53
  • The proof classifies the query’s effect on the database into five cases in the Hadamard basis and bounds each case separately.The cases distinguish transitions involving ⊥, |ˆ0⟩, and matching or distinct nonzero Hadamard states.Source: §H.1 · p. 54
  • Applying the inverse-oracle query twice on the same input uncomputes the database entry.The proof uses this relation to replace one state with another in bounding a hybrid difference.Source: §H.1 · p. 57
Loading 2609.40350v1…