Quantum Cryptanalysis

Since 2016, the U.S. National Institute of Standards and Technology has been running a standardization process for post-quantum public-key cryptography. So far, this process has produced one standard for a key encapsulation mechanism (Kyber / ML-KEM) and three standards for digital signature schemes (Dilithium / ML-DSA, Falcon / FN-DSA, and SPHINCS+ / SLH-DSA). Three of these standards are currently drafts open for public comment. At the same time, NIST is continuing to look at post-quantum KEMs, and has begun an additional process for standardizing more signature schemes. This talk will give an overview of this process and what the future might hold.

Quantum attacks using superposition queries are known to break many classically secure modes of operation. While these attacks do not necessarily threaten the security of the modes themselves, since they rely on a strong adversary model, they help us to draw limits on the provable security of these modes.

Typically these attacks use the structure of the mode (stream cipher, MAC or authenticated encryption scheme) to embed a period-finding problem, which can be solved with a dedicated quantum algorithm. The hidden period can be recovered with a few superposition queries (e.g., $O(n)$ for Simon’s algorithm), leading to state or key-recovery attacks. However, this strategy breaks down if the period changes at each query, e.g., if it depends on a nonce.

In this talk, we focus on this case and give dedicated state-recovery attacks on the authenticated encryption schemes Rocca, Rocca-S, Tiaoxin-346 and AEGIS-128L. These attacks rely on a procedure to find a Boolean hidden shift with a single superposition query, which overcomes the change of nonce at each query. As they crucially depend on such queries, we stress that they do not break any security claim of the authors, and do not threaten the schemes if the adversary only makes classical queries.

In the talk we surveyed quantum algorithms relevant to isogeny-based cryptography. One aspect of isogenies is that one can instantiate cryptographic group actions with them that still retain certain properties of discrete logarithms but are not susceptible to attacks via Shor’s algorithm. We discussed certain reductions between hard problems related to group actions most importantly the quantum equivalence of inverting the group action and the computational Diffie-Hellman problem (and that such an equivalence is highly unlikely in the classical setting as it would mean that the discrete logarithm and factoring assumptions do not hold). We also discussed recent quantum attacks on pSIDH utilizing a non-abelian hidden subgroup problem and improved quantum algorithms for finding fixed degree isogenies.

The Quantum Fourier Transform is a fundamental tool in quantum cryptanalysis. In symmetric cryptanalysis, hidden shift algorithms such as Simon’s (FOCS 1994), which rely on the QFT, have been used to obtain structural attacks on some very specific block ciphers. The Fourier Transform is also used in classical cryptanalysis, for example in FFT-based linear key-recovery attacks introduced by Collard et al. (ICISC 2007). Whether such techniques can be adapted to the quantum setting has remained so far an open question.

In this paper, we introduce a new framework for quantum linear key-recovery attacks using the QFT. These attacks loosely follow the classical method of Collard et al., in that they rely on the fast computation of a “correlation state” in which experimental correlations, rather than being directly accessible, are encoded in the amplitudes of a quantum state. The experimental correlation is a statistic that is expected to be higher for the good key, and on some conditions, the increased amplitude creates a speedup with respect to an exhaustive search of the key. The same method also yields a new family of structural attacks, and new examples of quantum speedups beyond quadratic using classical known-plaintext queries.

In this talk, I survey some algorithmic problems that arise from the cryptanalysis of lattice-based crytographic schemes such as the Shortest Vector problem and the Learning with Errors problem. Then I particularly focus on how quantum algorithms can help us obtain speed-ups on different approaches to solve those problems.

One of the founding results of lattice based cryptography is a quantum reduction from the Short Integer Solution problem to the Learning with Errors problem introduced by Regev. It has recently been pointed out by Chen, Liu and Zhandry that this reduction can be made more powerful by replacing the learning with errors problem with a quantum equivalent, where the errors are given in quantum superposition. In the context of codes, this can be adapted to a reduction from finding short codewords to a quantum decoding problem for random linear codes.

We therefore consider in this paper the quantum decoding problem, where we are given a superposition of noisy versions of a codeword and we want to recover the corresponding codeword. When we measure the superposition, we get back the usual classical decoding problem for which the best known algorithms are in the constant rate and error-rate regime exponential in the codelength. However, we will show here that when the noise rate is small enough, then the quantum decoding problem can be solved in quantum polynomial time. Moreover, we also show that the problem can in principle be solved quantumly (albeit not efficiently) for noise rates for which the associated classical decoding problem cannot be solved at all for information theoretic reasons.

We then revisit Regev’s reduction in the context of codes. We show that using our algorithms for the quantum decoding problem in Regev’s reduction matches best known quantum algorithms for the short codeword problem. This shows in some sense the tightness of Regev’s reduction when considering the quantum decoding problem and also paves the way for new quantum algorithms for the short codeword problem.

The lattice isomorphism problem (LIP) consists in finding a secret isometry between two input Euclidean lattices. LIP is a fundamental problem that has been studied for decades. Recently, Ducas and van Woerden proposed cryptosystems whose security rely on the presumed hardness of LIP. The known algorithms for the resolution of LIP rely on the calculation of short vectors in the input lattices. The shortest vector problem is a notoriously hard problem, even for quantum computers. This suggests that cryptosystems based on LIP might feature quantum resistance.

No quantum algorithms for the resolution of LIP have ever been described in the literature. The best classical algorithms for computing an isomorphism between two given lattices run in time $n^n$ (or $2^{n/2}$ if one of the input lattices is ${\mathbb{Z}}^n$). Finding a quantum algorithm with a better complexity than the existing classical algorithms for the resolution of LIP is an open problem.

Our group investigated quantum algorithms for the resolution of LIP. Several avenues were considered:

• $\mathrm{■}$

  We rephrased LIP as a hidden shift problem, which is a task that can (in certain cases) be solved efficiently by quantum computers.

• $\mathrm{■}$

  We reviewed the generation of instances of the LIP that are used for the creation of cryptographic keys. We studied conditions on the parameters that can make the LIP-based cryptosystems insecure.

• $\mathrm{■}$

  We studied quantum analogues of the existing classical algorithms for the resolution of LIP.

• $\mathrm{■}$

  We researched quantum algorithms to compute short vectors in lattices that are rotations of ${\mathbb{Z}}^n$, which is a task for which there exist ad-hoc classical solutions that outperform generic methods.

The work in our breakout group focused on Regev’s recent d-dimensional variation [1] of Shor’s quantum factoring algorithm ([2], [3]), and on better understanding its advantages and disadvantages in practical implementations.

Of particular interest to our group was the very recent Fibonacci-based arithmetic [4] that seemingly resolves reversibility issues previously identified by Ekerå and Gidney in Regev’s binary tree-based arithmetic.

There were presentations of ongoing work, including work [5] on extending Regev’s algorithm to computing discrete logarithms, and work ([6], [7]) on simulating the quantum parts of the algorithms for integers of known factorization and for groups where computing discrete logarithms is classically easy.

The aforementioned simulators enable the heuristic assumptions in Regev’s analysis to be verified. Furthermore, they enable the robustness of the classical post-processing to erroneous runs to be analyzed – where an erroneous run is a run in which the error correction fails to properly correct all errors, leading to a bad vector being output. There was discussion in the group regarding options for filtering out good vectors from bad vectors.

For the extension to discrete logarithms to be efficient, it is required that the group has a notion of small elements, that when composed yield elements that are also small, and where the composition of small elements is considerably less expensive than the composition of arbitrary group elements. A notion of small elements exists for ${\mathbb{Z}}_p^{\ast }$. There was discussion in the group regarding whether a similar notion exists for elliptic curve groups.