PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Attacks without Superposition Queries: the Offline Simon's Algorithm

Xavier Bonnetain, Akinori Hosoyamada, María Naya-Plasencia, Yu Sasaki, André Schrottenloher

arXiv:2002.12439v1quant-phcs.CR

TL;DR

Simon-based quantum attacks on symmetric cryptography have achieved strong results with superposition queries, while Q1 attacks with classical online queries had more limited speedups. This paper reuses Simon’s algorithm offline to exploit cryptosystem algebraic structure. It gives an Even-Mansour attack with O(2^n/3) classical queries and Õ(2^n/3) offline quantum computations, and reduces online quantum queries for an FX attack to O(n).

  • Problem

    Simon-based attacks can break symmetric constructions with superposition queries, but those results do not improve attacks when the adversary has only classical access, and Q1 speedups had been limited.

    Source: §1 · pp. 2–3

  • Method

    The paper reuses an offline-prepared quantum state in Grover search, using Simon’s algorithm to test candidate key guesses without superposition queries to the stored function.

    Source: §1 · p. 4, §7 · p. 29

  • Results

    The Even-Mansour attack uses O(2^n/3) classical queries and Õ(2^n/3) offline quantum computations, while the FX attack uses O(n) online quantum queries and Õ(2^m/2) offline quantum computations.

    Source: §1 · pp. 5–6

  • Takeaways & Limitations

    The paper finds that algebraic structure enabling superposition attacks can also make a practical difference for Q1 attacks.

    Source: §7 · p. 30

    The algorithm cannot attack schemes that do not have an attack in the superposition model.

    Source: §7 · p. 30

Abstract

from arXiv · show

In symmetric cryptanalysis, the model of superposition queries has led to surprising results, with many constructions being broken in polynomial time thanks to Simon's period-finding algorithm. But the practical implications of these attacks remain blurry. In contrast, the results obtained so far for a quantum adversary making classical queries only are less impressive. In this paper, we introduce a new quantum algorithm which uses Simon's subroutines in a novel way. We manage to leverage the algebraic structure of cryptosystems in the context of a quantum attacker limited to classical queries and offline quantum computations. We obtain improved quantum-time/classical-data tradeoffs with respect to the current literature, while using only as much hardware requirements (quantum and classical) as a standard exhaustive search with Grover's algorithm. In particular, we are able to break the Even-Mansour construction in quantum time $\tilde{O}(2^{n/3})$, with $O(2^{n/3})$ classical queries and $O(n^2)$ qubits only. In addition, we improve some previous superposition attacks by reducing the data complexity from exponential to polynomial, with the same time complexity. Our approach can be seen in two complementary ways: \emph{reusing} superposition queries during the iteration of a search using Grover's algorithm, or alternatively, removing the memory requirement in some quantum attacks based on a collision search, thanks to their algebraic structure. We provide a list of cryptographic applications, including the Even-Mansour construction, the FX construction, some Sponge authenticated modes of encryption, and many more.

1 Introduction

The introduction argues that Simon-based attacks had delivered strong results with superposition queries, while Q1 attacks with classical online queries had achieved limited speedups and could require substantial quantum hardware. The paper presents an offline use of Simon’s algorithm to attack in the Q1 model and reduce quantum-query costs in some Q2 attacks.

1 Introduction

  • The paper targets a gap between Q2 attacks, which offer low complexity but require superposition queries, and Q1 attacks, which had yielded only limited speedups.The introduction also identifies small quantum memory as a practical consideration for Q1 attacks.Source: §1 · pp. 2–3
  • The approach also reduces superposition queries in some Q2 attacks to polynomial order and converts an adaptive attack to a non-adaptive one.The introduction presents these as improvements alongside completely removing superposition queries in Q1 attacks.Source: §1 · p. 4
  • The new Q1 approach applies Simon’s algorithm without superposition queries to g when the state |ψg⟩ is available.The introduction describes preparing and reusing this state, allowing a period test of f ⊕ g as part of a Grover search.Source: §1 · pp. 4–5
  • The Even-Mansour attack recovers the keys with O(2^n/3) classical queries and Õ(2^n/3) offline quantum computations, using polynomially many qubits.It guesses 2n/3 key bits with Grover search and tests each guess using Simon’s algorithm on the remaining n/3 bits.Source: §1 · pp. 4–5
  • The FX attack uses O(n) online quantum queries and Õ(2^m/2) offline quantum computations, exponentially improving quantum-query complexity over Leander and May’s attack [31].The improvement comes from separating online queries from offline computations, rather than alternating them during Grover iterations.Source: §1 · p. 6

2 Preliminaries

The preliminaries set out the circuit and oracle model, then review Simon’s period-finding and Grover’s search algorithms. They also note that the paper’s algorithms do not require qRAM.

2.1 The Quantum Circuit Model

  • Quantum circuits use reversible unitary operations on qubits, with intermediate measurements deferrable until the computation ends.The paper counts logical quantum operations and qubits rather than physical implementation costs.Source: §2.1 · p. 7
  • Simon’s, Grover’s, and Shor’s algorithms do not require qRAM when their oracle calls do not require it.The paper contrasts this with quantum collision search, whose optimal speedup may require massive qRAM.Source: §2.1 · p. 8

2.2 Simon’s Algorithm

  • Simon’s algorithm uses superposition queries to recover a hidden Boolean period, and its success probability remains high when the period function may have random collisions.Under the stated conditions, it returns the period with probability at least 1 − 2^n · (3/4)^(cn).Source: §2.2 · pp. 8–9

2.3 Grover’s Algorithm

  • Grover’s algorithm searches for an input satisfying a test with a quadratic speedup over classical exhaustive search.It iteratively amplifies the amplitudes of inputs that pass the test.Source: §2.3 · p. 10

3 Simon’s Algorithm with Asymmetric Queries

The section formulates asymmetric search for an index whose function has a hidden period when combined with a shared function. Its algorithms reuse quantum data for that shared function, yielding Q2 methods with fewer queries and Q1 methods using classical queries to the shared function.

3 Simon’s Algorithm with Asymmetric Queries

  • The asymmetric-search problem asks for the unique index i_0 whose f_i0 ⊕ g has a hidden period, and for that period.The formulation distinguishes quantum access to F from classical or quantum access to g, depending on the model.Source: §3 · p. 10

3.1 Existing Techniques to Solve the Problem

  • In Q2, previous methods combine Grover search over indices with Simon testing, querying both F and g for each candidate.The cited prior approach tests a guessed key using O(n) queries to each function.Source: §3.1 · p. 11

3.2 An Algorithm for Asymmetric Search of a Shift

  • Alg-PolyQ2 reuses a stored quantum state for g while Grover-searching indices and testing whether each f_i ⊕ g has a hidden period.The testing procedure restores the g-database up to errors, allowing it to be reused across iterations.Source: Two observations · p. 12, Algorithm Alg-PolyQ2(informal) · pp. 12–13
  • Alg-PolyQ2 finds i_0 with probability Θ(1), using O(n) quantum queries to g and quantum queries to F.The supplied result states the O(n) query count for g; it does not give a complete count for F.Source: Algorithm Alg-PolyQ2(informal) · p. 13
  • Alg-PolyQ2 reduces queries to the keyed oracle by preparing its quantum data once and separating online queries from offline computation.The algorithm uses O(n) superposition queries to g; the paper describes this as removing superposition queries to g from the repeated search iterations.Source: Algorithm Alg-PolyQ2(informal) · p. 15, §3.3 · p. 15

3.3 Asymmetric Search with Q1 Queries

  • Alg-ExpQ1 replaces quantum queries to g with O(2^n) classical queries to prepare its quantum state before the offline search.The search then takes O(2^(m/2)) iterations, with quantum queries to F.Source: §3.3 · p. 15, Algorithm Alg-ExpQ1(informal) · p. 16
  • SimQ1 recovers the period with probability at least 1 − 2^n · (3/4)^(cn), using O(2^n) classical queries to g and cn quantum queries to f_i0.This is the period-finding step after identifying the index; Alg-ExpQ1 itself returns the index but not the period.Source: Finding actual periods · pp. 16–17

4 Q2 Attacks on Symmetric Schemes with Reduced Query Complexity

This section applies Alg-PolyQ2 to symmetric schemes, reducing quantum queries to keyed oracles compared with prior Q2 attacks at the same time cost. For FX, the method recovers keys with O(n) quantum queries.

4 Q2 Attacks on Symmetric Schemes with Reduced Query Complexity

  • Alg-PolyQ2 reduces quantum queries to keyed oracles exponentially compared with previous Q2 attacks, while retaining the same time cost.The section applies this result to symmetric schemes, including FX.Source: §4 · p. 17

4.1 An Attack on the FX construction

  • The FX attack recovers its keys with high probability using O(n) quantum queries to the keyed online oracle.The attack applies Alg-PolyQ2 to identify the inner key, then uses Simon’s algorithm to recover the whitening key and computes the remaining key efficiently.Source: Application of our algorithm Alg-PolyQ2 · pp. 18–19
  • For DESX, PRINCE, and PRIDE, the paper estimates roughly 135, 155, and 155 quantum queries, respectively.The corresponding estimated cipher-circuit computations are 2^29 for DESX and 2^33 for PRINCE and PRIDE.Source: Applications to DESX, PRINCE and PRIDE · p. 19

5 Q1 Attacks on Symmetric Schemes

Alg-ExpQ1 uses classical queries to prepare Simon-related states, then performs Simon and Grover computations offline, yielding tradeoffs for Q1 attacks on symmetric schemes with polynomial resources. Applications cover Even-Mansour and FX key recovery, as well as Chaskey and sponge-based modes.

5.1 Tradeoffs for the Even-Mansour Construction

  • For Even-Mansour, the attack achieves D · T^2 = 2^n with polynomial qubits and classical space, balancing at T = D = Õ(2^(n/3)).It divides k1 into two parts, using Simon’s algorithm to recover one part and offline Grover search to guess the other.Source: Application of Alg-ExpQ1 · pp. 21–22
  • For Farfalle, the one-block construction degenerates to Even-Mansour, but the cited instance estimates exceed direct key exhaustive search for Kravatte and reach Xoofff’s data limit.The paper gives costs of 2^533 data and time for Kravatte versus at most 2^160 for direct key search; Xoofff requires 2^128 data and is relevant when its key size exceeds 256 bits.Source: Applications to concrete instances · pp. 22–23

5.2 Tradeoffs for the FX Construction

  • For FX, the attack achieves D · T^2 = 2^(n+m) for D ≤ 2^n, balancing at T = D = Õ(2^((n+m)/3)) when m ≤ 2n, with polynomial qubits and classical memory.The construction similarly combines Simon’s algorithm with offline Grover search over key information.Source: Previous Q1 attacks on the FX… · pp. 23–25
  • In XTS, a full codebook for one block can recover the first key and that block’s whitening keys; the second key can then be brute-forced using pairs from other blocks.Source: Application to concrete instances · p. 25

5.3 Other Applications

  • For Chaskey, the attack recovers K1 and then K by inverting π; with the 2^48 data limit, the estimated cost is about 2^59 quantum gates.The dominant cost is solving an 80-dimensional linear system in each Grover iteration.Source: Chaskey · p. 26
  • For sponge modes, the attack requires an input injected on a fixed state; its nonce must be fixed and its cost is at least 2^(c/2).The paper identifies Beetle as an applicable case: Beetle[Light+] uses 2^48 classical queries and Grover iterations, while Beetle[Secure+] uses 2^85 messages and iterations.Source: Sponges · pp. 26–27

6 Discussion

The discussion extends the attack idea to related-key and slide attacks, including a classical-query related-key attack and a hidden-period formulation for broader settings.

6.1 Related Keys

  • Related-key recovery was previously described as a collision search, while a superposition-query attack uses Simon’s algorithm to recover the hidden key.The cited superposition attack applies to any block cipher, including ideal ones.Source: §6.1 · p. 27
  • Grover search over k2 after querying n/3-bit differences reduces related-key key recovery from 2^(n/2) to 2^(n/3) quantumly.The related-key oracle remains classical.Source: §6.1 · p. 28
  • For Saturnin16, the result sets an expected Q1 related-key security level of 2^85, using 2^(n/3) classical related-key queries.The passage states that Saturnin16 has 256-bit blocks and that no Q1 related-key attack on it should have time complexity below 2^85.Source: §6.1 · p. 28

6.2 Slide Attacks

  • The slide-attack application constructs a function with hidden period (1, k1), enabling recovery of k1 and k2 using the attack strategy.The construction uses the iterated-FX relation described in the passage.Source: §6.2 · p. 28
  • Problem 4 generalizes the strategy to finding an index i0 and period s when composing Fi with g applied after permutation pi.The formulation allows classical or quantum access to g, with classical access in Q1; the paper relates the transformation to a generalization of CCZ equivalence.Source: §6.2 · p. 29

7 Conclusion

The paper presents an offline use of Simon’s algorithm that reuses compressed quantum data during Grover search. Its Even-Mansour attack reduces query-storage requirements, while the approach applies only to schemes with the relevant algebraic structure.

7 Conclusion

  • The algorithm reuses compressed superposition-query data during Grover-search iterations, applying Simon’s algorithm’s core idea offline without quantum oracle queries.The paper describes this as its first example of Simon’s algorithm used in an offline setting.Source: §7 · p. 29
  • The approach cannot attack schemes lacking an attack in the superposition model, and the authors call for further investigation of this boundary.The paper attributes the Q1 results to algebraic structure that makes superposition attacks possible.Source: §7 · p. 30

A Proofs for Propositions 2 and 3

The appendix analyzes errors in the testing procedure used during Grover search and their effect on the search’s overall success probability.

A Proofs for Propositions 2 and 3

  • The testing procedure is intended to check whether each candidate i is good using auxiliary quantum data |ψg⟩.The analysis considers both Alg-ExpQ1 and Alg-PolyQ2.Source: A Proofs for Propositions 2 and 3 · p. 33
  • In practice, each test can err and slightly modify the auxiliary state |ψg⟩.The appendix therefore analyzes both the test’s error and its effect on the full Grover search.Source: A Proofs for Propositions 2 and 3 · p. 33
  • The appendix uses general quantum amplitude amplification analysis to assess how test errors affect search success, then proves Propositions 2 and 3.The analyses are divided between Sections A.1 and A.2, with the propositions proved in A.3.Source: A Proofs for Propositions 2 and 3 · p. 33

A.1 Error Analyses for the testing procedure test

The testing unitary is intended to distinguish whether a candidate function has a period, but the procedure only achieves this with small error.

A.1 Error Analyses for the testing procedure test

  • The state |ψg⟩ is defined for a function g and fixed positive integer c.Source: §A.1 · p. 33
  • The test is intended to flip an output bit when fi ⊕ g has a period, while leaving the candidate and auxiliary state unchanged.The intended behavior is approximate rather than exact.Source: §A.1 · p. 33
  • The test’s imperfect output and its slight modification of |ψg⟩ are the two error sources analyzed for Grover search.The appendix separately studies the test’s error and its effect on overall search success.Source: §A.1 · p. 33

1. Query cn times to F to obtain

The test uses the span dimension of sampled vectors to check whether an index is good, distinguishing periodic from non-periodic cases. A lemma bounds its error when the non-periodic functions satisfy the stated condition and the sample count is sufficiently large.

1. Query cn times to F to obtain

  • A periodic f_i ⊕ g makes the test flip b, while a non-periodic function can still produce an error term.For each sampled tuple, the test adds 1 to b when the vectors do not span the full space and 0 otherwise.Source: §1 · p. 34
  • When c is sufficiently large, a lemma guarantees that the test behaves as expected, with its error vector bounded under the stated condition.The proof notes that the condition holds when the f_i in F0 are almost random and far from periodic.Source: §1 · pp. 34–35
  • The proof reduces the error analysis to a single f_i and bounds the probability that sampled vectors fail to span the full space.Such a rank deficiency occurs exactly when a nonzero vector is orthogonal to every sampled vector.Source: §1 · p. 36

A.2 Error Propagation Analyses for QAA

Quantum amplitude amplification can increase the probability of obtaining a good output, but this analysis allows the checking procedure to be imperfect. The paper bounds the resulting success probability loss in terms of the checker error and the number of iterations.

The Original Quantum Amplitude Amplification

  • In the original QAA setup, r iterations of Q amplify the good-output probability, with r chosen from θ_a such that sin^2 θ_a = a.The ideal success probability is at least max(1 − a, a).Source: The Original Quantum Amplitude… · p. 38

Our Setting: Uncertain Checking Procedures

  • The analysis models checking with a unitary that approximates the ideal phase-checking procedure, with error at most ε for each input and auxiliary state.In the attack, this approximate checking operator is the test procedure.Source: Our Setting: Uncertain Checking… · p. 38
  • For checking error ǫ of c S′χ, measuring Q′rA|0n⟩|ψ⟩ yields an x satisfying χ(x) = 1 with probability at least max(1 −a, a) −4rǫ.Source: Our Setting: Uncertain Checking… · p. 39

A.3 Finishing the Proofs

Given the state |ψ_g⟩ and the stated assumptions, the offline phases of Alg-ExpQ1 and Alg-PolyQ2 find a good index with constant probability. Their analysis applies quantum amplitude amplification with an uncertain checking procedure.

A.3 Finishing the Proofs

  • With m in O(n), sufficiently large c, and the stated assumption, the offline phases find a good index with probability Θ(1), using O(2^m/2) quantum queries to F and time O((n^3 + nT_F)2^m/2).The state |ψ_g⟩ is given; the offline computation excludes the procedures that prepare it.Source: §A.3 · p. 40
  • The proof applies uncertain-checking amplitude amplification with error ε = 2^(n+1)/2(3/4)^(cn/2) and initial good fraction a = 1/2^m.It uses O(2^m/2) Grover iterations; for sufficiently large c and m in O(n), the resulting success probability is Θ(1).Source: §A.3 · pp. 40–41
  • Each Grover iteration uses O(n) queries to F and takes time O(n^3 + nT_F).The time includes computing the dimension of the span of the sampled vectors.Source: §A.3 · p. 41

B Adaptive Attacks and Non-Adaptive Attacks

The paper distinguishes adaptive from non-adaptive attacks by construction and query model. Its FX attack in the Q2 model and the discussed Q1 attacks are non-adaptive.

B Adaptive Attacks and Non-Adaptive Attacks

  • The FX attack in the Q2 model is non-adaptive because its online queries use only the uniform superposition of plaintexts.Unlike the previous Q2 attack by Leander and May, its keyed online queries do not depend on earlier quantum-query results.Source: B Adaptive Attacks and Non-Adaptive… · p. 41
Loading 2002.12439v1…