Paper 2022/1337

How to Enumerate LWE Keys as Narrow as in Kyber/Dilithium

Abstract

In the Learning with Errors (LWE) problem we are given a matrix $A \in \mathbb{Z}_q^{N \times N}$ and a target vector $\vec{t} \in \mathbb{Z}_q^N$ such that there exists small-norm $\vec{s}, \vec{e}\in \mathbb{Z}_q^N$ satisfying $A\cdot\vec{s} = \vec{t} + \vec{e} \bmod q$. Modern cryptosystems often sample $\vec{s}, \vec{e}$ from narrow distributions that take integer values in a small range $[-\eta, \eta].$ Kyber and Dilithium both choose $\eta=2$ and $\eta=3$ using either a Centered Binomial distribution (Kyber), or a uniform distribution (Dilithium). In this work, we address the fundamental question how hard the enumeration of LWE secret keys for narrow distributions with $\eta \leq 3$ is. At Crypto 21, May proposed a representation-based algorithm for enumerating ternary keys, i.e. the case $\eta = 1$, with a fixed number of $\pm 1$ entries. In this work, we extend May's algorithm in several ways. First, we show how to deal with keys sampled from a probability distribution as in many modern systems like Kyber and Dilithium, rather than with keys having a fixed number of entries. Second, we generalize to larger values $\eta= 2, 3$, thereby achieving asymptotic key guess complexities that are not far off from lattice estimates. E.g. for Kyber's Centered Binomial distribution we achieve heuristic time/memory complexities of $\mathcal{O}(2^{0.36N})$ for $\eta=2$, and $\mathcal{O}(2^{0.37N})$ for $\eta=3$. For Dilithium's uniform distribution we achieve heuristic complexity $\mathcal{O}(2^{0.38N})$ for $\eta=2$. Let $S$ be the Shannon entropy of Kyber/Dilithium keys. Then our algorithms runs in time about ${S}^{\frac 16}$, which greatly improves over the standard combinatorial Meet-in-the-Middle attack with complexity ${S}^{\frac 1 2}$. Our results also compare well to current lattice asymptotics of $2^{0.29 \beta}$, where the lattice parameter $\beta$ is roughly of size $\frac 4 5 N$. Thus, our analysis supports that Kyber secret keys are indeed hard to enumerate. Yet, we find it remarkable that a purely combinatorial key search is almost competitive with highly evolved lattice sieving techniques.