International Association
for Cryptologic Research

In LWE-based KEMs, observed decryption errors leak information about the secret key in the form of equations or inequalities. Several practical fault attacks have already exploited such leakage by either directly applying a fault or enabling a chosen-ciphertext attack using a fault. When the leaked information is in the form of inequalities, the recovery of the secret key is not trivial. Recent methods use either statistical or algebraic methods (but not both), with some being able to handle incorrect information. Having in mind that integration of the side-channel information is a crucial part of several classes of implementation attacks on LWEbased schemes, it is an important question whether statistically processed information can be successfully integrated in lattice reduction algorithms.We answer this question positively by proposing an error-tolerant combination of statistical and algebraic methods that make use of the advantages of both approaches. The combination enables us to improve upon existing methods – we use both fewer inequalities and are more resistant to errors. We further provide precise security estimates based on the number of available inequalities.Our recovery method applies to several types of implementation attacks in which decryption errors are used in a chosen-ciphertext attack. We practically demonstrate the improved performance of our approach in a key-recovery attack against Kyber with fault-induced decryption errors.

The Shortest Vector Problem (SVP) is one of the mathematical foundations of lattice based cryptography. Lattice sieve algorithms are amongst the foremost methods of solving SVP. The asymptotically fastest known classical and quantum sieves solve SVP in a d-dimensional lattice in $$2^{\mathsf {c}d + o(d)}$$ time steps with $$2^{\mathsf {c}' d + o(d)}$$ memory for constants $$c, c'$$ . In this work, we give various quantum sieving algorithms that trade computational steps for memory.We first give a quantum analogue of the classical k-Sieve algorithm [Herold–Kirshanova–Laarhoven, PKC’18] in the Quantum Random Access Memory (QRAM) model, achieving an algorithm that heuristically solves SVP in $$2^{0.2989d + o(d)}$$ time steps using $$2^{0.1395d + o(d)}$$ memory. This should be compared to the state-of-the-art algorithm [Laarhoven, Ph.D Thesis, 2015] which, in the same model, solves SVP in $$2^{0.2653d + o(d)}$$ time steps and memory. In the QRAM model these algorithms can be implemented using $$\mathrm {poly}(d)$$ width quantum circuits.Secondly, we frame the k-Sieve as the problem of k-clique listing in a graph and apply quantum k-clique finding techniques to the k-Sieve.Finally, we explore the large quantum memory regime by adapting parallel quantum search [Beals et al., Proc. Roy. Soc. A’13] to the 2-Sieve, and give an analysis in the quantum circuit model. We show how to solve SVP in $$2^{0.1037d + o(d)}$$ time steps using $$2^{0.2075d + o(d)}$$ quantum memory.