Quantum Cryptanalysis

Shor’s quantum algorithm for integer factorization compels us to rethink currently deployed cryptographic schemes in order to make them post-quantum, that is, resistant even to adversaries equipped with a functional quantum computer. These new schemes rely on novel computational assumptions, notably those based on Euclidean lattices and error-correcting codes. In recent years, a new family of quantum algorithms targeting these lattice and code-based problems has been discovered. These algorithms are inspired by Regev’s reduction, which constitutes one of the theoretical foundations of post-quantum cryptography. This presentation will offer an overview of this family of algorithms, along with a discussion of their implications for post-quantum cryptography and, more broadly, for quantum algorithms.

The assumed hardness of the Shortest Vector Problem in high-dimensional lattices is one of the cornerstones of post-quantum cryptography. The fastest known heuristic attacks on SVP are via so-called sieving methods. While these still take exponential time in the dimension $d$, they are significantly faster than non-heuristic approaches, and their heuristic assumptions are verified by extensive experiments. $k$-Tuple sieving is an iterative method where each iteration takes as input a large number of lattice vectors of a certain norm, and produces an equal number of lattice vectors of slightly smaller norm, by taking sums and differences of $k$ of the input vectors. Iterating these “sieving steps” sufficiently many times produces a short lattice vector. The fastest attacks (both classical and quantum) are for $k=2$, but taking larger $k$ reduces the amount of memory required for the attack. In this paper, we improve the quantum time complexity of 3-tuple sieving from $2^{0.3098d}$ to $2^{0.2846d}$, using a two-level amplitude amplification aided by a preprocessing step that associates the given lattice vectors with nearby “center points” to focus the search on the neighborhoods of these center points. Our algorithm uses $2^{0.1887d}$ classical bits and QCRAM bits, and $2^{o(d)}$ qubits. This is the fastest known quantum algorithm for SVP when total memory is limited to $2^{0.1887d}$.

Kuperberg’s algorithm is a subexponential time algorithm for the dihedral hidden subgroup problem. This tutorial presented the algorithm in detail, also serving as an example of what a quantum algorithm looks like, for those new to the field.

(Talk abstract written by S. Jeffery.)

In this discussion, we first clarified the distinction between different types of quantum and classical memory, and then had a lively discussion about which models are physically realistic. We reached a general consensus that it is important to always clarify the specific memory resources your quantum algorithms require.

(Talk abstract written by S. Jeffery.)

In this calk, we study the fundamental problem of guessing cryptographic keys, drawn from some probability distribution D. The optimal classical algorithm enumerates keys in decreasing order of likelihood. The optimal quantum algorithm, due to Montanaro (2011), is a sophisticated Grover search.

We give the first tight analysis for Montanaro’s algorithm, showing that its runtime is $2^{H_{2/3}(D)/2}$, where $H_{\alpha }$ denotes Renyi entropy with parameter $\alpha$. Interestingly, this is a direct consequence of an information theoretic result called Arikan’s Inequality (1995) – which has so far been missed in the cryptographic community – that tightly bounds the runtime of classical key guessing by $2^{H_{1/2}(D)}$,.

Since for every non-uniform distribution $𝔻$, we thus obtain a super-quadratic quantum speed-up over classical key guessing.

Additonally, we provide the first thorough analysis of guessing in a multi-key setting.

In this talk I introduced higher modules of syzygies for codes, and associated notions (minmal resolution, graded Betti numbers). I then explained how, applied to a suitable shortening of the dual code, these invariants allow to distinguish binary Goppa codes (as they appear in the McEliece cryptosystem) from random codes. The asymptotic complexity of this distinguisher is (slightly) subexponential in the error-correcting capability, which is better than any previous cryptanalytic attempt against the McEliece cryptosystem (either targetting the key or the messages). Last, I briefly discussed work in progress and recent advances that occurred after this work was presented at Eurocrypt 2025.

Searching for collisions in random functions is a fundamental computational problem, with many applications in symmetric and asymmetric cryptanalysis. When one searches for a single collision, the known quantum algorithms match the query lower bound. This is not the case for the problem of finding multiple collisions, despite its regular appearance as a sub-component in sieving-type algorithms.

At EUROCRYPT 2019, Liu and Zhandry gave a query lower bound $\mathrm{\Omega }(2^{m/3+2k/3})$ for finding $2^k$ collisions in a random function with $m$-bit output. At EUROCRYPT 2023, Bonnetain et al. gave a quantum algorithm matching this bound for a large range of $m$ and $k$, but not all admissible values. Like many previous collision-finding algorithms, theirs is based on the MNRS quantum walk framework, but it chains the walks by reusing the state after outputting a collision.

In this talk, we give a new algorithm that tackles the remaining non-optimal range, closing the problem. Our algorithm is tight (up to a polynomial factor) in queries, and also in time under a quantum RAM assumption. The idea is to extend the chained walk to a regime in which several collisions are returned at each step, and the “walks” themselves only perform a single diffusion layer.

In this talk I will survey the currently known algorithms for solving the Lattice Isomorphism Problem (LIP) and its module version (Module-LIP). The latter case also involves some quantum steps, which can optionally be removed with additional assumptions and heuristics.

There is a recent family of quantum algorithm based on Regev’s reduction that has gained a lot of attention recently. In its modern formulation, this is a reduction between the Inhomogeneous Short Integer Solution Problem (ISIS) to the |S-LWE⟩ which is a variant of LWE where the error is in quantum superposition. For constructing quantum algorithms, this framework has first been presented by Chen, Liu and Zhandry and there have since been many works trying to leverage this reduction for solving code and lattice-based problems which are classically intractable. This approach has been quite successful and we have several examples of powerful quantum algorithms. However, the problems that can be attacked are still far from real problems used in post-quantum cryptography.

The idea of this working group was to have a general discussion on this family of algorithms. The main question was to determine whether these can have a strong impact on quantum cryptanalysis and therefore on the foundations of current post-quantum cryptography. We touched on the following questions:

• $\mathrm{■}$

  Find structured codes/lattices for which these algorithms yield a quantum advantage.

• $\mathrm{■}$

  Apart from Gaussian Elimination and the Arora-Ge algorithm, do we have access to other “generic” algorithms for LWE that we can use?

• $\mathrm{■}$

  Can we “quantize” these algorithms so that they are more efficient in the presence of quantum noise?

• $\mathrm{■}$

  Do we have access to more tools from quantum information theory than just (partial) unambiguous measurements?

• $\mathrm{■}$

  Can we say something about the classical hardness that these problems have or can we dequantize these quantum algorithms?

• $\mathrm{■}$

  How far are we from attacking a system like DILITHIUM with these algorithms?

The conclusion of this working group is that while the approach is promising, we don’t yet have examples where this can be directly used for lattice-based problems and that one requires a more in-depth understanding of the |S-LWE> and the differences with the LWE problem in order to fully take advantage of this approach.

The discussion in the breakout group first centered on the practicability of Regev’s algorithm [10, 3]. The conclusion of the group was that although the new parallel spooky pebbling-based approach [7] reduces the circuit size and depth compared to earlier Fibonacci-based approaches [9, 8], it is still hard to see a niche for Regev’s algorithm where it would be of practical interest unless further optimizations are found or non-computational space is cheap.

The group considered various metrics that may be useful in comparing quantum algorithms when coarse-grained metrics such as that used in [4] no longer suffice to distinguish the best implementation, including but not limited to the space usage, depth, gate count and spacetime volume, both per-run and overall, and both logically and physically. The group agreed that in the short to medium term, algorithms and implementation techniques that achieve a small space footprint, most notably [11, 5, 2, 1, 6], are currently arguably the best option. In the long term, what matters most is arguably the spacetime volume across all runs (qubits times depth), and here too it appears hard for Regev’s algorithm to compete given the number of runs it requires (not least when considering the overhead of quantum error correction).

Furthermore, the group discussed options for parallelizing the pre-Regev algorithms when a similar amount of space is available as that required by Regev’s algorithm. With respect to parallelization, the group agreed that limited parallelization in [6] may be beneficial, as opposed to sequentially processing the many small primes. This would result in fairly substantial depth reduction at the expense of only a small increase in the space usage.

Finally, the group considered options for further reducing the space required to store the control registers in [1, 6], for instance via recycling some of the qubits. However, the conclusion of the group was that it would take new ideas to achieve such a space reduction without incurring a space blowup in other parts of the circuit.

A first goal of this working group was to help participants get more familiarity or intuition with higher modules of syzygies. We then presented various algorithms to compute syzygies:

• $\mathrm{■}$

  the iterative approach, following the definitions

• $\mathrm{■}$

  a direct approach through Koszul cohomology.

We then discussed possible techniques (classical or quantum) that could speed-up the underlying linear algebra:

• $\mathrm{■}$

  block Wiedemann type techniques

• $\mathrm{■}$

  the HHL algorithm.

Last we tried to identify other possible applications of syzygies in cryptanalysis.

This working group explored open questions related to block cipher cryptanalysis using the quantum convolution algorithm (QCA). This is a family of statistical attacks where the statistic of interest is expressed as a convolution, and used to distinguish right and wrong key guesses. We targeted in particular two problems.

The first problem was the use of convolution-based cryptanalysis in the case of zero-correlation linear attacks. In these linear attacks, the statistic for the right key guess becomes zero. Unfortunately in the quantum setting, it is the amplitude over the key itself which becomes zero, which is useless. We tried different manipulations of the QCA output which would have improved this situation, especially using independent zero-correlation statistics. Unfortunately our attempts in this direction failed.

The second problem was to make use of precomputations in the attack. Indeed, the computation of the QCA, at least in linear cryptanalysis, is not the dominating cost of the attack. We tried different approaches to gain a better advantage by pre-amplifying the output of the QCA. One of these attempts worked: we obtained a block cipher structure on which a non-trivial attack could be mounted. This attack can be seen roughly as a combination of Meet-in-the-middle cryptanalysis with linear cryptanalysis, which warrants further investigation.