Skip to content

Latest commit

 

History

History
193 lines (136 loc) · 9.28 KB

README.rst

File metadata and controls

193 lines (136 loc) · 9.28 KB
Raw

Security Estimates for Lattice Problems

Documentation Status

This Sage module provides functions for estimating the concrete security of Learning with Errors instances.

The main purpose 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.

Quick Start

We currently provide evaluators for the security of the LWE, NTRU, and SIS problems. Our estimator integrates simulators for the best known attacks against these problems, and provides bit-security estimates relying on heuristics to predict the cost and shape of lattice reduction algorithms. The default models are configured in conf.py.

It is possible to evaluate attacks cost individually, or using the helper functions:

  • *.estimate.rough: fast routine that evaluates the security of the problem only against the usually most efficient attacks. Note that it uses a non-default cost model for lattice reduction, most often used in the literature for ease of comparison, and will thus return different numbers than the rest of the API. Refer to its documentation for details.
  • *.estimate: extended routine that evaluates the security of the problem against all supported attacks. This uses the default cost and shape model for lattice reduction.

Usage examples:

>>> from estimator import *
>>> schemes.Kyber512
LWEParameters(n=512, q=3329, Xs=D(σ=1.22), Xe=D(σ=1.22), m=512, tag='Kyber 512')

>>> LWE.primal_usvp(schemes.Kyber512)
rop: ≈2^143.8, red: ≈2^143.8, δ: 1.003941, β: 406, d: 998, tag: usvp

>>> r = LWE.estimate.rough(schemes.Kyber512)
usvp                 :: rop: ≈2^118.6, red: ≈2^118.6, δ: 1.003941, β: 406, d: 998, tag: usvp
dual_hybrid          :: rop: ≈2^115.5, red: ≈2^115.3, guess: ≈2^112.3, β: 395, p: 5, ζ: 0, t: 40, β': 395, N: ≈2^81.4, m: 512

>>> r = LWE.estimate(schemes.Kyber512)
bkw                  :: rop: ≈2^178.8, m: ≈2^166.8, mem: ≈2^167.8, b: 14, t1: 0, t2: 16, ℓ: 13, #cod: 448, #top: 0, #test: 64, tag: coded-bkw
usvp                 :: rop: ≈2^143.8, red: ≈2^143.8, δ: 1.003941, β: 406, d: 998, tag: usvp
bdd                  :: rop: ≈2^140.3, red: ≈2^139.7, svp: ≈2^138.8, β: 391, η: 421, d: 1013, tag: bdd
dual                 :: rop: ≈2^149.9, mem: ≈2^97.1, m: 512, β: 424, d: 1024, ↻: 1, tag: dual
dual_hybrid          :: rop: ≈2^139.7, red: ≈2^139.6, guess: ≈2^135.9, β: 387, p: 5, ζ: 0, t: 50, β': 391, N: ≈2^81.1, m: 512
>>> from estimator import *
>>> schemes.Dilithium2_MSIS_WkUnf
SISParameters(n=1024, q=8380417, length_bound=350209, m=2304, norm=+Infinity, tag='Dilithium2_MSIS_WkUnf')

>>> r = SIS.estimate.rough(schemes.Dilithium2_MSIS_WkUnf)
lattice  :: rop: ≈2^123.5, red: ≈2^123.5, sieve: ≈2^-332.2, β: 423, η: 423, ζ: 1, d: 2303, prob: 1, ↻: 1, tag: infinity

>>> r = SIS.estimate(schemes.Dilithium2_MSIS_WkUnf)
lattice  :: rop: ≈2^152.2, red: ≈2^151.3, sieve: ≈2^151.1, β: 427, η: 433, ζ: 0, d: 2304, prob: 1, ↻: 1, tag: infinity
>>> from estimator import *
>>> schemes.Falcon512_SKR
NTRUParameters(n=512, q=12289, Xs=D(σ=4.05), Xe=D(σ=4.05), m=512, tag='Falcon512_SKR', ntru_type='circulant')

>>> r = NTRU.estimate.rough(schemes.Falcon512_SKR)
usvp                 :: rop: ≈2^140.5, red: ≈2^140.5, δ: 1.003499, β: 481, d: 544, tag: usvp

>>> r = NTRU.estimate(schemes.Falcon512_SKR)
usvp                 :: rop: ≈2^165.1, red: ≈2^165.1, δ: 1.003489, β: 483, d: 1020, tag: usvp
bdd                  :: rop: ≈2^160.6, red: ≈2^159.6, svp: ≈2^159.6, β: 463, η: 496, d: 1022, tag: bdd
bdd_hybrid           :: rop: ≈2^160.6, red: ≈2^159.6, svp: ≈2^159.6, β: 463, η: 496, ζ: 0, |S|: 1, d: 1024, prob: 1, ↻: 1, tag: hybrid
bdd_mitm_hybrid      :: rop: ≈2^349.3, red: ≈2^349.3, svp: ≈2^204.8, β: 481, η: 2, ζ: 0, |S|: 1, d: 1024, prob: ≈2^-182.6, ↻: ≈2^184.8, tag: hybrid

>>> schemes.Falcon512_Unf
SISParameters(n=512, q=12289, length_bound=5833.9072, m=1024, norm=2, tag='Falcon512_Unf')

>>> r = SIS.estimate.rough(schemes.Falcon512_Unf)
lattice  :: rop: ≈2^121.2, red: ≈2^121.2, δ: 1.003882, β: 415, d: 1024, tag: euclidean

>>> r = SIS.estimate(schemes.Falcon512_Unf)
lattice  :: rop: ≈2^146.4, red: ≈2^146.4, δ: 1.003882, β: 415, d: 1024, tag: euclidean

Status

We cover:

We are planning:

  • [ ] attack on SIS instances

Evolution

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. We recommend to also state the commit that was used when referencing this project.

Warning

We give no API/interface stability guarantees. We try to be mindful but we may reorganize the code without advance warning.

Bugs

Please report bugs through the GitHub issue tracker.

Contributions

At present, this estimator is maintained by Martin Albrecht. Contributors are:

See Contributing for details on how to contribute.

Citing

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

An updated version of the material covered in the above survey is available in Rachel Player's PhD thesis.

License

The estimator is licensed under the LGPLv3+ license.

Third Party Tools Using this Estimator

Acknowledgements

This project was supported through the European Union PROMETHEUS project (Horizon 2020 Research and Innovation Program, grant 780701), EPSRC grant EP/P009417/1 and EPSRC grant EP/S020330/1, by Zama and by SandboxAQ.