Lattice estimator fails to run (with all attacks) for lattice dimension 2^15 or higher, i.e., larger q

[yspolyakov]

@sararv22

When we try to run the lattice estimator with all attack techniques, we get various errors. Some example inputs and outputs are provided below. These were run on a Xeon server with 72 cores on Ubuntu.

Example 1:

Input

params = LWE.Parameters(n=2^15, q=2^881, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
LWE.estimate(params, red_cost_model=RC.BDGL16, jobs = 64)

Output (shortly after starting)

Algorithm functools.partial(<function dual_hybrid at 0x7fca661143a0>, red_cost_model=<estimator.reduction.BDGL16 object at 0x7fca663dd0a0>, mitm_optimization=False) on LWEParameters(n=32768, q=16122269626942909129404900662735492142298807557254685123533957184651913530173488143140175045399694454793530120643833272670970079330526292030350920973600450955456136596649325078391464772840162385651374295294530896122681527488756156580761624107880751845994219387748352, Xs=D(σ=0.82), Xe=D(σ=3.19), m=+Infinity, tag=None) failed with unable to convert to MPFR (exponent out of range?)

Example 2:

Input

params = LWE.Parameters(n=2^15, q=2^981, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
LWE.estimate(params, red_cost_model=RC.BDGL16, jobs = 64)

Output (after 3-4 hours)

NaN result encountered

Example 3:

Input

params = LWE.Parameters(n=2^15, q=2^1281, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
LWE.estimate(params, red_cost_model=RC.BDGL16, jobs = 64)

Output (shortly after starting)

Algorithm <estimator.lwe_bkw.CodedBKW object at 0x7fca6634fd60> on LWEParameters(n=32768, q=41631728778657596327700961309456342154461048989066819221276449401614432238693441192048957766929296739369686455817124031165534264993293859632559626422709283051696518037556881383092733398646334201891837682190759244846774708590193915467850005537753041166929395541244643314153666340113022418664899327563675207388272888812562084106793741954931832115512203478944747602858882842222812674916352, Xs=D(σ=0.82), Xe=D(σ=3.19), m=+Infinity, tag=None) failed with ECL says: #<a FLOATING-POINT-OVERFLOW>

When we exclude the hybrid attacks, i.e.,

LWE.estimate(params, red_cost_model=RC.BDGL16, deny_list=["bkw", "bdd_hybrid", "bdd_mitm_hybrid", "dual_hybrid", "dual_mitm_hybrid", "arora-gb"],jobs = 64)

the lattice estimator runs successfully.

All three exceptions seem to be related to handling large floating-point numbers (close or above the range for doubles).