[Resource Topic] 2022/1337: How to Enumerate LWE Keys as Narrow as in Kyber/Dilithium

Welcome to the resource topic for 2022/1337

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

Authors: Timo Glaser, Alexander May


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.

ePrint: https://eprint.iacr.org/2022/1337

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .