estimator.lwe_primal.PrimalUSVP

estimator.lwe_primal.PrimalUSVP#

class estimator.lwe_primal.PrimalUSVP[source]#

Estimate cost of solving LWE via uSVP reduction.

__call__(params: ~estimator.lwe_parameters.LWEParameters, red_cost_model=<estimator.reduction.MATZOV object>, red_shape_model='gsa', optimize_d=True, log_level=1, **kwds)[source]#

Estimate cost of solving LWE via uSVP reduction.

Parameters:

  • params – LWE parameters.

  • red_cost_model – How to cost lattice reduction.

  • red_shape_model – How to model the shape of a reduced basis.

  • optimize_d – Attempt to find minimal d, too.

Returns:

A cost dictionary.

The returned cost dictionary has the following entries:

  • rop: Total number of word operations (≈ CPU cycles).

  • red: Number of word operations in lattice reduction.

  • δ: Root-Hermite factor targeted by lattice reduction.

  • β: BKZ block size.

  • d: Lattice dimension.

EXAMPLE:

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

>>> params = LWE.Parameters(n=200, q=127, Xs=ND.UniformMod(3), Xe=ND.UniformMod(3))
>>> LWE.primal_usvp(params, red_shape_model="cn11")
rop: ≈2^87.5, red: ≈2^87.5, δ: 1.006114, β: 209, d: 388, tag: usvp

>>> LWE.primal_usvp(params, red_shape_model=Simulator.CN11)
rop: ≈2^87.5, red: ≈2^87.5, δ: 1.006114, β: 209, d: 388, tag: usvp

>>> LWE.primal_usvp(params, red_shape_model=Simulator.CN11, optimize_d=False)
rop: ≈2^87.6, red: ≈2^87.6, δ: 1.006114, β: 209, d: 400, tag: usvp

>>> params = LWE.Parameters(n=384, q=2**7, Xs=ND.Uniform(0, 1), Xe=ND.CenteredBinomial(8), m=2*384)
>>> LWE.primal_usvp(params, red_cost_model=RC.BDGL16)  # Issue #87
rop: ≈2^161.8, red: ≈2^161.8, δ: 1.003634, β: 456, d: 595, tag: usvp

>>> Xe=ND.DiscreteGaussian(stddev=3.19)
>>> params = LWE.Parameters(n=1030, m=2060, q=2**64, Xs=ND.Uniform(0, 1), Xe=Xe)
>>> LWE.primal_usvp(params, red_cost_model=RC.BDGL16)  # Issue #95
rop: ≈2^53.1, red: ≈2^53.1, δ: 1.010374, β: 78, d: 1933, tag: usvp

# small n examples (Issue #181)
>>> params = LWE.Parameters(n=11, q = 2**128, Xs=ND.UniformMod(2**128), Xe=ND.UniformMod(2**124))
>>> LWE.primal_usvp(params)
rop: ≈2^126.0, red: ≈2^126.0, δ: 1.004356, β: 351, d: 455, tag: usvp
>>> LWE.primal_usvp(params, red_shape_model=Simulator.CN11)
rop: ≈2^127.1, red: ≈2^127.1, δ: 1.004315, β: 356, d: 443, tag: usvp

The success condition was formulated in [USENIX:ADPS16] and studied/verified in [AC:AGVW17], [C:DDGR20], [PKC:PosVir21]. The treatment of small secrets is from [ACISP:BaiGal14].

Methods

__init__()

Attributes

cost_gsa

cost_simulator

Contents