How to Enumerate LWE Keys as Narrow as in Kyber/Dilithium
Timo Glaser, Ruhr University Bochum
Alexander May, Ruhr University Bochum
Abstract
In the Learning with Errors (LWE) problem we are given a matrix and a target vector such that there exists small-norm satisfying .
Modern cryptosystems often sample from narrow distributions that take integer values in a small range Kyber and Dilithium both choose and 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 is. At Crypto 21, May proposed a representation-based algorithm for enumerating ternary keys, i.e. the case , with a fixed number of 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 , 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 for , and for . For Dilithium's uniform distribution we achieve heuristic complexity for .
Let be the Shannon entropy of Kyber/Dilithium keys. Then our algorithms runs in time about , which greatly improves over the standard combinatorial Meet-in-the-Middle attack with complexity .
Our results also compare well to current lattice asymptotics of , where the lattice parameter is roughly of size . 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.
@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},
url = {https://eprint.iacr.org/2022/1337}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.