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 smallnorm $\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 representationbased 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 MeetintheMiddle 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.
Metadata
 Available format(s)
 Category
 Attacks and cryptanalysis
 Publication info
 Preprint.
 Contact author(s)

timo glaser @ rub de
alex may @ rub de  History
 20221010: approved
 20221007: received
 See all versions
 Short URL
 https://ia.cr/2022/1337
 License

CC BY
BibTeX
@misc{cryptoeprint:2022/1337, author = {Timo Glaser and Alexander May}, title = {How to Enumerate LWE Keys as Narrow as in Kyber/Dilithium}, howpublished = {Cryptology ePrint Archive, Paper 2022/1337}, year = {2022}, note = {\url{https://eprint.iacr.org/2022/1337}}, url = {https://eprint.iacr.org/2022/1337} }