Estimation of the Hardness of the Learning with Errors Problem with a Given Number of Samples

26.01.2017, 11:00 – 12:00

2017/01/26 11:00-12:00

Speaker: Markus Schmidt | Location: Hochschulstraße 10 (S2|02), Piloty Building, Room B002, Darmstadt

Organizer: Prof. Johannes Buchmann / Moritz Horsch


Lattice-based cryptography is a promising candidate to build cryptographic primitives that are secure even against quantum algorithms. The Learning with Errors problem (LWE) is one of the most important hardness assumptions, lattice-based construction base their security on. Recently, Albrecht et al. (Journal of Mathematical Cryptology 2015) presented the Sage module “LWE-Estimator” to estimate the hardness of LWE instances, making the choice of parameters for lattice-based primitives easier and better comparable. The effectiveness of algorithms to solve LWE is often depending on the number of LWE instances, called LWE-samples, given. Therefore, the optimal number of LWE-samples is assumed to estimate the hardness.

In cryptographic aplications the optimal number of samples is often not given, but only a smaller number of samples. This leads to a more conservative choice of parameters than necessary in applications. This work aims to improve the parameter choice with respect to described problem. The contribution presented in this work is twofold. First, we analyze the hardness of LWE instances given a fixed number of samples. For this, we describe algorithms proposed in literature to solve LWE shortly and estimate their computational cost while taking a limitation of the available number of samples into account.

We consider instances of generic LWE as well as instances with small secret. Secondly, we use these results to extend the Sage module “LWE-Estimator”, so that the resulting implementation can be used to estimate LWE instances with fixed numbers of samples. Furthermore, we present examples of using the implementation and show estimation results using example parameters. These indicate a significant impact on the hardness of LWE if the number of samples is strongly limited. Also, we show a comparison of the considered algorithms, focusing on the behavior when limiting the number of available samples.