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.6, red: ≈2^87.6, δ: 1.006114, β: 209, d: 388, tag: usvp

>>> LWE.primal_usvp(params, red_shape_model=Simulator.CN11)
rop: ≈2^87.6, red: ≈2^87.6, δ: 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

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