Arora-GB
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))