Paper 2020/539

On the Concrete Security of LWE with Small Secret

Hao Chen, Lynn Chua, Kristin Lauter, and Yongsoo Song

Abstract

Lattice-based cryptography is currently under consideration for standardization in the ongoing NIST PQC Post-Quantum Cryptography competition, and is used as the basis for Homomorphic Encryption schemes world-wide. Both applications rely specifically on the hardness of the Learning With Errors (LWE) problem. Most Homomorphic Encryption deployments use small secrets as an optimization, so it is important to understand the concrete security of LWE when sampling the secret from a non-uniform, small distribution. Although there are numerous heuristics used to estimate the running time and quality of lattice reduction algorithms such as BKZ2.0, more work is needed to validate and test these heuristics in practice to provide concrete security parameter recommendations, especially in the case of small secret. In this work, we introduce a new approach which uses concrete attacks on the LWE problem as a way to study the performance and quality of BKZ2.0 directly. We find that the security levels for certain values of the modulus q and dimension n are smaller than predicted by the online LWE Estimator, due to the fact that the attacks succeed on these uSVP lattices for blocksizes which are smaller than expected based on current estimates. We also find that many instances of the TU Darmstadt LWE challenges can be solved significantly faster when the secret is chosen from the binary or ternary distributions.