estimator.gb.AroraGB#
- class estimator.gb.AroraGB[source]#
- __call__(params: LWEParameters, success_probability=0.99, omega=2, log_level=1, **kwds)[source]#
Arora-GB as described in [ICALP:AroGe11], [EPRINT:ACFP14].
- Parameters:
params – LWE parameters.
success_probability – targeted success probability < 1.
omega – linear algebra constant.
- Returns:
A cost dictionary
The returned cost dictionary has the following entries:
rop
: Total number of word operations (≈ CPU cycles).m
: Number of samples consumed.dreg
: The degree of regularity or “solving degree”.t
: Polynomials of degree 2t + 1 are considered.mem
: Total memory usage.
EXAMPLE:
>>> from estimator import * >>> params = LWE.Parameters(n=64, q=7681, Xs=ND.DiscreteGaussian(3.0), Xe=ND.DiscreteGaussian(3.0), m=2**50) >>> LWE.arora_gb(params) rop: ≈2^307.1, m: ≈2^46.8, dreg: 99, t: 25, mem: ≈2^307.1, tag: arora-gb
TESTS:
>>> LWE.arora_gb(params.updated(m=2**120)) rop: ≈2^282.6, m: ≈2^101.1, dreg: 83, t: 36, mem: ≈2^282.6, tag: arora-gb >>> LWE.arora_gb(params.updated(Xe=ND.UniformMod(7))) rop: ≈2^60.6, dreg: 7, mem: ≈2^60.6, t: 3, m: ≈2^30.3, tag: arora-gb >>> LWE.arora_gb(params.updated(Xe=ND.CenteredBinomial(8))) rop: ≈2^122.3, dreg: 19, mem: ≈2^122.3, t: 8, m: ≈2^50.0, tag: arora-gb >>> LWE.arora_gb(params.updated(Xs=ND.UniformMod(5), Xe=ND.CenteredBinomial(4), m=1024)) rop: ≈2^227.2, dreg: 54, mem: ≈2^227.2, t: 4, m: 1024, tag: arora-gb >>> LWE.arora_gb(params.updated(Xs=ND.UniformMod(3), Xe=ND.CenteredBinomial(4), m=1024)) rop: ≈2^189.9, dreg: 39, mem: ≈2^189.9, t: 4, m: 1024, tag: arora-gb >>> Xs, Xe =ND.SparseTernary(1024, 64, 0), ND.DiscreteGaussian(2**10) >>> LWE.arora_gb(LWE.Parameters(n=1024, q=2**40, Xs=Xs, Xe=Xe)) rop: ≈2^inf, dreg: ≈2^inf, tag: arora-gb
[EPRINT:ACFP14]Martin R. Albrecht, Carlos Cid, Jean-Charles Faugère & Ludovic Perret. (2014). Algebraic algorithms for LWE. https://eprint.iacr.org/2014/1018
[ICALP:AroGe11]Sanjeev Aror & Rong Ge. (2011). New algorithms for learning in presence of errors. In L. Aceto, M. Henzinger, & J. Sgall, ICALP 2011, Part I (pp. 403–415).: Springer, Heidelberg.
Methods
__init__
()cost_Gaussian_like
(params[, ...])Estimate cost using absolute bounds for secrets and Gaussian tail bounds for noise.
cost_bounded
(params[, success_probability, ...])Estimate cost using absolute bounds for secrets and noise.
equations_for_secret
(params)Return
(d,n)
tuple to encode that n equations of degree d are available from the LWE secret.ps_single
(C)Probability that a Gaussian is within C standard deviations.