International Association
for Cryptologic Research

We study the practicality of a primal hybrid lattice attack on LWE. Despite significant research efforts, the state-of-the-art in practical LWE record computations so far is the plain primal attack with Kannan's embedding. Building on an idea by Espitau and Fouque, Bernstein proposed in 2023 an LWE hybrid attack that asymptotically outperforms the primal attack. In a nutshell, Bernstein's attack enumerates some coordinates of an LWE key and uses the sophisticated Batch-CVP (Randomized) Slicer algorithm to solve LWE in a dimension-reduced lattice. The practical implications of this attack however remain widely unclear. One of the major obstacles for judging practicality is the lack of a fast, fully functional Slicer implementation. For the first time, we provide an efficient Slicer implementation that includes all required algorithmic ingredients like locality sensitive hashing. Building on our Slicer implementation, we implement a generalization of Bernstein's algorithm. While Bernstein's attack works only for LWE, ours also applies to a more general BDD setting. Let (B,t) be a BDD instance, where the target t is off from the d-dimensional lattice L(B) by some error e, sampled coordinate-wise from a distribution D. We show that for hard BDD instances, our BDD hybrid asymptotically speeds up primal's complexity of T=2^{0.292d + o(d)} down to T^{1-K}, where K \approx (1+H(D)/0.058)^{-1} with H(D) the Shannon entropy. Depending on D, the constant K can be small, making practical improvements difficult. We test our Slicer-based implementation inside an implementation of our BDD hybrid lattice attack to tackle LWE instances. We choose two ternary LWE secrets with different entropies H(D) as used in NTRU, and the centered binomial distribution as used in Kyber. For all three distributions in all tested LWE dimensions n \in [160, 210], our Slicer-based implementation practically demonstrates measurable speedups over the primal attack, up to a factor of 5. We also show that for parameters as originally suggested by Regev, the hybrid attack cannot improve over primal.