Arora-GB

We construct an (easy) example LWE instance and estimate the cost of solving it using Gröbner bases as described in [ICALP:AroGe11], [EPRINT:ACFP14]:

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)

The cost of this approach – Arora-GB – depends on the number of samples:

LWE.arora_gb(params.updated(m=2^120))

If the noise distribution is bounded, this bounds the absolute degree and thus cost:

LWE.arora_gb(params.updated(Xe=ND.UniformMod(7)))

Centered binomial distributions are also bounded:

LWE.arora_gb(params.updated(Xe=ND.CenteredBinomial(8)))

The secret plays its role, too, in reducing the cost of solving:

LWE.arora_gb(params.updated(Xs=ND.UniformMod(5), Xe=ND.CenteredBinomial(4), m=1024))

LWE.arora_gb(params.updated(Xs=ND.UniformMod(3), Xe=ND.CenteredBinomial(4), m=1024))