PaperlayerView exact revision on arXiv

Source-linked AI summary

Quantum Differential and Linear Cryptanalysis

Marc Kaplan, Gaëtan Leurent, Anthony Leverrier, María Naya-Plasencia

arXiv:1510.05836v3quant-phcs.CR

TL;DR

This paper examines how quantum computing affects symmetric-cipher security through quantum versions of differential and linear cryptanalysis. It finds that these attacks often gain a quadratic speed-up, but not uniformly, so the best classical attack need not remain the best quantum attack.

  • Problem

    Symmetric cryptography needs a more accurate analysis of its security against quantum adversaries because existing work had only partially studied quantum attacks on symmetric constructions.

  • Method

    The paper develops quantum differential and linear cryptanalytic techniques using quantum search and amplitude amplification, and analyzes them in different adversary models.

  • Results

    Quantum differential and linear attacks usually obtain a quadratic gain, but truncated differential attacks gain less, making the optimal quantum attack potentially different from the optimal classical attack.

  • Takeaways & Limitations

    Quantum symmetric cryptanalysis must be studied directly rather than by simply quantizing the best classical attack, because attack rankings can change between classical and quantum settings.

  • Takeaways & Limitations

    Some parameter regimes invalidate the described procedure and require a different checking algorithm, so the attack analysis is not uniform across all parameters.

Abstract

from arXiv · show

Quantum computers, that may become available one day, would impact many scientific fields, most notably cryptography since many asymmetric primitives are insecure against an adversary with quantum capabilities. Cryptographers are already anticipating this threat by proposing and studying a number of potentially quantum-safe alternatives for those primitives. On the other hand, symmetric primitives seem less vulnerable against quantum computing: the main known applicable result is Grover's algorithm that gives a quadratic speed-up for exhaustive search. In this work, we examine more closely the security of symmetric ciphers against quantum attacks. Since our trust in symmetric ciphers relies mostly on their ability to resist cryptanalysis techniques, we investigate quantum cryptanalysis techniques. More specifically, we consider quantum versions of differential and linear cryptanalysis. We show that it is usually possible to use quantum computations to obtain a quadratic speed-up for these attack techniques, but the situation must be nuanced: we don't get a quadratic speed-up for all variants of the attacks. This allows us to demonstrate the following non-intuitive result: the best attack in the classical world does not necessarily lead to the best quantum one. We give some examples of application on ciphers LAC and KLEIN. We also discuss the important difference between an adversary that can only perform quantum computations, and an adversary that can also make quantum queries to a keyed primitive.

1 Introduction

Quantum computing motivates a closer examination of symmetric-cipher security because classical cryptanalysis underpins confidence in designs, while quantum attacks may alter the effectiveness and ranking of attack techniques. The paper develops quantum versions of differential and linear cryptanalysis and distinguishes adversaries with classical versus quantum oracle queries.

  • Motivation: Grover’s algorithm gives exhaustive key search a quadratic speed-up, motivating more accurate analysis than simply doubling key lengths.The paper notes that little work had addressed this question before its study of quantum cryptanalytic techniques.
  • Motivation: Symmetric-cipher security is heuristic and depends on cryptanalysis, security evaluations, and margins measured against reduced-round designs.These evaluations help compare designs and detect whether a cipher is close to being broken.
  • Approach: The paper studies quantum versions of differential, truncated differential, and linear cryptanalysis to assess their impact on symmetric ciphers.It presents this as a first synthetic treatment of how these attacks are affected by quantum computing.
  • Scope: Classical security proofs for modes of operation do not always transfer to quantum settings, so block-cipher analysis must be combined with mode-security analysis.The paper cites Q2 breaks of common MAC and authenticated-encryption modes alongside quantum-secure encryption-mode results.
  • Results: Differential and linear attacks usually gain quadratically in the Q2 model, whereas truncated differential attacks usually gain less.Q2 adversaries can make quantum queries to the keyed primitive, unlike Q1 adversaries, which collect data classically and process it quantumly.
  • Results: The optimal quantum attack need not be the quantum version of the optimal classical attack.The paper also reports that Q1 gains may be small when key and block lengths match but significant for longer keys.

2 Preliminaries

The preliminaries formalize the block-cipher setting, key-recovery and distinguishing goals, attack-complexity measures, and the paper’s quantum treatment of differential and linear attacks. The analysis compares classical and quantum versions while omitting success probability from the stated parameters.

  • Block-cipher setting: A block cipher E has blocksize n, keysize k, and r rounds; E^(t) denotes its t-round reduced version.The attacker seeks the secret key κ* used by the oracle encryption E(x)=E_κ*(x).
  • Attack goals: Brute-force key recovery has complexity 2^k, defining the ideal security against which faster attacks are compared.A cipher is considered broken when its key can be found with fewer encryptions than generic brute force.
  • Complexity measures: Attack efficiency is measured by data, time, and memory complexity.Data complexity counts oracle calls, while oracle-query time is included in time complexity.
  • Attack goals: Distinguishers distinguish a concrete cipher from an ideal one and can indicate a weakness that often supports key recovery.They are less powerful than key-recovery attacks.
  • Quantum attack setting: The paper quantizes differential and linear attack families for distinguishing and last-round key-recovery variants, including simple and truncated differentials.This provides a first step toward quantizing symmetric cryptanalytic families.
  • Assumptions: Success probability is omitted because it affects classical and quantum versions similarly and can be increased by a constant-factor data adjustment.The comparison therefore focuses on the attack parameters rather than success-probability differences.

3 Quantum algorithms

The paper builds quantum attacks from search, amplitude amplification, quantum counting, and collision-finding procedures. These algorithms provide quadratic improvements in suitable settings but introduce output-superposition and nesting considerations.

  • Quantum attacks target complexities below the generic Grover exhaustive-search cost of 2^(k/2).
  • The framework parameterizes search by setup cost S and checking cost C, which may measure time or input queries.
  • Amplitude amplification raises a good-output probability a to constant success using a quadratic improvement over classical repetition.
  • Quantum counting estimates the fraction of marked elements using D queries with bounded success probability and controlled error.
  • Ambainis’ algorithm finds collisions in O(n^2/3) time and extends to related pairs at average cost O(n^2/3 k^-1/3).
  • Quantum-walk outputs can remain entangled with memory data, creating issues when such procedures are nested inside arbitrary quantum algorithms.

4 Differential Cryptanalysis

Differential cryptanalysis studies how input differences propagate through a cipher and uses resulting output differences to analyze attacks against block ciphers.

  • Differential cryptanalysis tracks input differences δin and their influence on output differences δout.

4.1 Classical Adversary

The classical differential attacks first distinguish a cipher from a random function, then extend the distinguisher into a last-round key-recovery attack. Their costs depend on differential probabilities, filtering, partial-key generation, and exhaustive completion.

  • Classical distinguisher: A classical differential distinguisher uses 2^hS input pairs and has data and time complexity 2^(hS+1).
  • Last-rounds attack: A last-rounds attack extends an R-round distinguisher by adding rounds and reduces exhaustive key search from 2^k to a smaller partial-key space.
  • Last-rounds attack: The final-round filtering uses Dfin, Δfin, hout, and kout to construct partial-key candidates from pairs surviving the output-difference test.
  • Last-rounds attack: Completing surviving partial keys over the remaining k−kout bits costs 2^(hS+Δfin−n+k−hout), while lists can be processed on the fly.
  • Attack criterion: The attack is effective when its time complexity is lower than exhaustive search, with data complexity separately denoted for the attack.

4.2 Quantum Adversary

Quantum differential attacks use Grover-style searches with quantum setup and checking procedures, in both Q2 and Q1 models. Their speedups depend on the attack variant, data access, and partial-key generation costs.

  • Q2 adversary: In the Q2 model, Grover search finds a message satisfying the differential condition using superposition queries to the cipher.
  • Q2 adversary: Q2 attacks avoid explicitly creating lists by querying the cryptographic algorithm whenever list sampling is needed.
  • Q2 adversary: The Q2 procedure checks partial keys, then completes them with Grover search over the remaining k−kout bits.
  • Q2 adversary: The marked-element probability is lower bounded by ε ≥ 2^(−hS−Δfin+n), determining the search effort for a successful differential pair.
  • Q1 adversary: In the Q1 model, data acquisition remains classical, while quantum operations accelerate partial-key generation and search after filtering.
  • Q1 adversary: Classical attacks with data complexity below the square root of exhaustive key search can translate into effective Q1 attacks, especially for larger keys.
  • Partial-key generation: Quantum partial-key generation can reduce a worst-case classical cost up to 2^kout, with Grover-based cost 2^(kout/2) when kout < hout.

5 Truncated Differential Cryptanalysis

Truncated differential cryptanalysis replaces fixed differences with input and output difference sets, enabling structures that reduce classical data complexity. Quantum algorithms can accelerate collision searches, but the Q1 model offers no advantage and the overall speedup is not always quadratic.

  • Classical truncated differentials: 2^2Δin−1 pairs can be generated from one structure of size 2^Δin, reducing data complexity relative to simple differential attacks.A structure provides many plaintext pairs whose input differences lie in Din.
  • Classical truncated differentials: 2^hT candidate pairs suffice for a distinguisher because one valid pair is likely while random functions rarely produce an output difference in Dout.The distinguisher checks whether E(x) ⊕ E(y) belongs to Dout.
  • Classical truncated differentials: Truncated differentials use sets of input and output differences rather than two fixed bit strings.The analysis assumes vector spaces Din and Dout and probability 2^-hT for reaching Dout from Din.
  • Quantum truncated differentials: Q1 provides no advantage because data collection is the bottleneck, whereas Q2 can quantum-search collisions inside structures.Ambainis’ element-distinctness algorithm yields 2^(hT+1)/3 queries for a single structure, and Grover search combines structure selection with quantum checking when multiple structures are needed.
  • Quantum truncated differentials: The Q2 speedup is always less than quadratic, and some parameter regimes require replacing the ordinary Grover procedure with element-distinctness search.When 2^Δin−1−n+Δfin < 0, the expected search space has size below one, so the standard procedure is invalid.

6 Applications on existing ciphers

Applications to LAC and KLEIN show that quantizing a classical differential attack can change which attack is best or whether the cipher is broken. In particular, truncated differentials can lose their classical advantage in the quantum setting.

  • Applications: The applications compare classical and quantum differential attacks on LAC, KLEIN-64, and KLEIN-96.The examples are chosen to contrast the best classical and quantum attacks.
  • LAC: A truncated differential is more efficient than a simple differential classically, but the ordering reverses with a quantum computer.This comparison is the central counter-intuitive outcome of the LAC example.
  • LAC: For LAC, the best classical attack has complexity 2^60.9 for truncated differentials versus 2^62.5 for simple differentials, while the best quantum attack has complexity 2^31.75 for simple differentials.The quantum truncated attack has complexity about 2^33.4 and is less efficient than generic Grover search.
  • KLEIN-64: KLEIN-64 is broken classically with time complexity 2^58.2, but its quantum truncated-differential attack does not work because the relevant term becomes 2^34.75.The quantum exhaustive-search benchmark is 2^32, so the quantized attack is not faster than brute force.
  • KLEIN-64: KLEIN-64 remains secure against the quantum attack in both Q1 and Q2 models, despite being broken in the classical setting.Here, “broken” means faster-than-brute-force attack, which differs from practical insecurity.
  • KLEIN-96: For KLEIN-96, the Q2 attack has complexity 2^47.3 and still breaks the cipher, while the Q1 attack has complexity 2^47.96 and also remains below 2^48.The comparison benchmark is 2^48 quantum encryptions.

7 Linear Cryptanalysis

Linear cryptanalysis approximates a cipher’s nonlinear encryption function with correlated linear relations described by input and output masks. The paper constructs round-based approximations and evaluates their full-cipher correlation with the piling-up lemma.

  • Linear approximations: Linear cryptanalysis approximates the round function with a linear function correlated to the encryption function E.A one-round approximation relates masked input and output values with probability exceeding that of a random permutation.
  • Linear approximations: Linear masks describe the input and output selections used in each approximation.For a mask χ, the notation x[χ] denotes the XOR of selected input bits.
  • Linear approximations: Round approximations are chained by matching each round’s output mask to the next round’s input mask.The piling-up lemma evaluates the resulting correlation across the full cipher.
  • Quantum linear cryptanalysis: The paper assumes a known linear approximation and uses it with a quantum computer for distinguishing or key recovery.This section introduces the linear distinguishers and subsequent attack variants.

7.1 Classical Adversary

The classical adversary uses a known linear approximation to distinguish encryption from a random permutation or recover key bits. Last-round attacks instead test partial key guesses by partially decrypting ciphertexts and selecting the guess with the strongest bias.

  • Linear distinguisher: A linear distinguisher requires D = A/ε^2 known plaintext-ciphertext pairs and compares the observed bias with ε/2.The constant A controls the desired success probability and is omitted from asymptotic complexity.
  • Linear distinguisher: The observed bias is expected to be 0 for a random permutation and ε for the target encryption function.Hoeffding’s inequality bounds the distinguisher’s error probabilities, which decrease as A increases.
  • Key recovery: The sign of the bias reveals one key bit, and independent approximations can recover additional key bits.This turns a distinguisher into a key-recovery procedure when enough approximations are available.
  • Last-round attack: A last-round attack partially decrypts ciphertexts for each partial-key guess, accumulates counters, and selects the guess with maximal absolute counter value.The method uses an R-round distinguisher followed by partial decryption over rout final rounds.
  • Last-round attack: The described algorithm can be improved by distilling partial plaintext and ciphertext occurrence counts before the analysis phase.Some cases also permit FFT-based improvements, but the paper focuses on the simpler full-data analysis.

7.2 Quantum Adversary

In the Q2 model, quantum approximate counting reduces the data needed by a linear distinguisher quadratically, but key-recovery attacks do not automatically obtain the same improvement in data complexity. The attack strategies combine partial-key recovery with Grover search, with different procedures for Q1 and Q2 access.

  • Quantum distinguishers: O(1/ε) queries suffice for quantum approximate counting to achieve an ε-approximation.This counting procedure underlies the Q2 linear distinguisher.
  • Quantum distinguishers: The Q2 linear distinguisher achieves a quadratic speed-up compared to the classical distinguisher.The corresponding complexity is denoted Q2 = T lin. dist.
  • Key recovery: For ℓ linear relations, key recovery first obtains ℓ key bits and then applies Grover’s algorithm to recover the full key.Each relation recovers one key bit using 1/ε^2 data in the classical-model comparison described here.
  • Key recovery: A quadratic improvement in data complexity is not obtained a priori because classical attacks can reuse the same data, unlike the analyzed Grover procedure.The limitation concerns data complexity rather than the possibility of quantum computation itself.
  • Q1 and Q2 strategies: In the Q1 model, the attacker stores classical-model data in quantum memory and performs two successive Grover searches for a partial key and the remaining key.In the Q2 strategy, approximate counting improves the partial-key checking step within Grover search.

8 Discussion

The discussion shows that quantum differential and linear cryptanalysis generally provide square-root-cost attacks, but acceleration depends on the attack variant, query model, and cipher parameters. Consequently, the best classical attack need not remain best quantum attack, and longer keys can make quantum attacks more relevant.

  • Security implications: Quantum differential or linear attacks cost at least the square root of their corresponding classical attacks.Thus, classical resistance at cost 2^k implies resistance to the corresponding quantum attack at cost at least 2^(k/2).
  • Security implications: Quadratic quantum speed-up is not always possible, particularly for truncated attacks.The discussion attributes this limitation to the collision-finding step in truncated differential attacks.
  • Security implications: In the Q1 model, quantum differential or linear attacks retain the classical data complexity but can still outperform Grover search in important cases.Q1 permits only classical encryption queries, whereas Q2 permits quantum superposition queries; Q1 usually gives smaller acceleration.
  • Security implications: Longer keys can make quantum differential and linear attacks more threatening because key-dependent terms receive quadratic quantum improvement.For Q1 attacks, when k ≥ 2n, the data complexity is always smaller than 2^(k/2).
  • Security implications: Using longer keys can leave classical attacks that break a cipher leading to quantum attacks that also break it, even with only classical queries.This observation is presented as relevant to the recommended strategy of increasing key lengths against quantum adversaries.
  • Changing attack rankings: A truncated differential attack may be best classically while a simple differential attack becomes best quantumly.Therefore, directly quantizing the best known classical attack does not guarantee the best post-quantum attack.
  • Changing attack rankings: Differential attacks can beat brute force classically while their quantum versions are no faster than Grover’s algorithm.The paper identifies this counter-intuitive behavior in an example discussed in Section 6.2.1.

9 Conclusion and open questions

The paper advances a quantum symmetric-cryptanalysis toolbox through differential and linear attacks, while showing that quantum attack choice and attack models require separate study. Its conclusions identify concrete limits and open questions concerning speedups, attack construction, linear methods, and quantum access to ciphers.

  • Conclusion: Quantizing the best known classical differential attack may not produce the best quantum attack, so quantum attacks must be studied across cryptanalysis families.The paper presents this as a non-intuitive behavior motivating broader investigation of quantum attacks.
  • Conclusion: Quantum-walk techniques provide only polynomial speed-ups, with the largest gap being quadratic through Grover’s algorithm.These attacks can outperform quantum exhaustive search without implying a collapse of symmetric cryptography comparable to factoring-based public-key cryptography.
  • Open questions: The study leaves open whether quantum computers can discover useful differential characteristics or linear approximations rather than merely exploit supplied ones.The attacks begin with a given differential characteristic or linear approximation and use quantum algorithms for key recovery.
  • Open questions: Linear cryptanalysis remains limited to simple classical attacks, excluding constructions based on counters or the fast Fourier transform.The paper identifies quantum Fourier-transform-based acceleration of more involved linear cryptanalysis as a future direction.
  • Attack models: The Q2 model permits superposition access for consistency, whereas the more realistic Q1 model raises unresolved questions about transferring queried data into quantum processing.A cipher secure in Q2 remains secure in any setting, while Q1 may be too simplistic at the classical–quantum interface.
Loading 1510.05836v3…