Estimator for the Bit Security of LWE Instances
The main intend of this estimator is to give designers an easy way to choose parameters resisting known attacks and to enable cryptanalysts to compare their results and ideas with other techniques known in the literature.
sage: load("https://bitbucket.org/malb/lwe-estimator/raw/HEAD/estimator.py") sage: n, alpha, q = unpack_lwe(Regev(128)) sage: set_verbose(1) sage: costs = estimate_lwe(n, alpha, q, skip="arora-gb") sage: print cost_str(costs["dec"]) bop: ≈2^56.1, oracle: ≈2^14.5, δ_0: 1.0097372, bkz2: ≈2^55.0, k: 90, fplll: ≈2^126.0, sieve: ≈2^63.8, enum: ≈2^40.2, enumop: ≈2^55.3, ε: 0.0625000
Try it online
At present the following algorithms are covered by this estimator.
- exhaustive search + a meet-in-the-middle variant
- Coded-BKW [C:GuoJohSta15]
- lattice-reduction based distinguishing
- lattice-reduction based decoding [RSA:LinPei11]
- solving BDD via Kannan embedding as described in [ICISC:AlbFitGop13]
- using Gröbner bases to solve LWE [EPRINT:ACFP14]
For small secrets, the following variants are covered:
- exhaustive search + a meet-in-the-middle variant for small secrets
- modulus switching in combination with any of the algorithms mentioned above
- small-secret embedding [ACISP:BaiGal14]
- small-secret BKW [PKC:AFFP14]
- small, sparse secret dual lattice attacks [EPRINT:Albrecht17]
Above, we use cryptobib-style bibtex keys as references.
This code is evolving, new results are added and bugs are fixed. Hence, estimations from earlier versions might not match current estimations. This is annoying but unavoidable at present. We recommend to also state the commit that was used when referencing this project.
We also encourage authors to let us know if their paper uses this code. In particular, we thrive to tag commits with those cryptobib ePrint references that use it. For example, this commit corresponds to this ePrint entry.
Our intend is for this estimator to be maintained by the research community. For example, we encourage algorithm designers to add their own algorithms to this estimator and we are happy to help with that process.
More generally, all contributions such as bugfixes, documentation and tests are welcome. Please go ahead and submit your pull requests. Also, don’t forget to add yourself to the list of contributors below in your pull requests.
At present, this estimator is maintained by Martin Albrecht. Contributors are:
- Martin Albrecht
- Florian Göpfert
- Cedric Lefebvre
- Rachel Player
- Sam Scott
If you run into a bug, please open an issue on bitbucket. Also, please check there first if the issue has already been reported.
If you use this estimator in your work, please cite
Martin R. Albrecht, Rachel Player and Sam Scott.
On the concrete hardness of Learning with Errors.
Journal of Mathematical Cryptology.
Volume 9, Issue 3, Pages 169–203,
ISSN (Online) 1862-2984, ISSN (Print) 1862-2976
DOI: 10.1515/jmc-2015-0016, October 2015
A pre-print is available as
Cryptology ePrint Archive, Report 2015/046, 2015. https://eprint.iacr.org/2015/046
A high-level overview of that work is given, for instance, in this talk.