Lattice estimator is very slow for larger lattice dimensions (2^14 or higher)

[yspolyakov]

@sararv22

When we run the lattice estimator for larger lattice dimensions without hybrid attacks (note that it does not currently work for hybrid attacks at lattice dimension 2^15 or so, as pointed out in #74), we see runtimes dramatically higher than for the LWE estimator. These experiments were run on a Xeon server with 72 cores.

Example 1 (lattice dimension 2^14)

For

params = LWE.Parameters(n=2^14, q=2^438, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
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)

It takes 30 minutes (as compared to 2 minutes in LWE estimator)

For the case with hybrid attacks

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

It takes about 12-13 hours.

Example 2 (lattice dimension 2^15)

For

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, deny_list=["bkw", "bdd_hybrid", "bdd_mitm_hybrid", "dual_hybrid", "dual_mitm_hybrid", "arora-gb"],jobs = 64)

It takes 1 hour 40 minutes (as compared to 2 minutes in LWE estimator)

The case with hybrid attacks does not run, as documented in #74

In BGV BFV, and CKKS with bootstrapping we often need lattice (ring) dimensions of 2^16 and 2^17. How can we run the estimator for these larger lattice dimensions?

[malb]

FWIW, this is quick:

sage: from estimator import *
sage: params = LWE.Parameters(n=2^14, q=2^438, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
sage: LWE.estimate.rough(params)

so it might be worth comparing the results of the rough estimate with that of the full one and perhaps just use the rough estimates?

[malb]

Also, can you post some smaller scale examples that behave similarly but not quite so slowly? Easier to play with those. Say, n=1024, 2048 …

[sararv22]

FWIW, this is quick:

sage: from estimator import *
sage: params = LWE.Parameters(n=2^14, q=2^438, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
sage: LWE.estimate.rough(params)

so it might be worth comparing the results of the rough estimate with that of the full one and perhaps just use the rough estimates?

We got significantly different work factor estimates for LWE.estimate.rough vs LWE.estimate. Below is the output of both for params n = 2^14, q = 2^438:

params = LWE.Parameters(n=2^14, q=2^438, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19))
LWE.estimate.rough(params)
usvp:: rop: ≈2^93.7, red: ≈2^93.7, δ: 1.004628, β: 321, d: 31988, tag: usvp
dual_hybrid:: rop: ≈2^93.7, mem: ≈2^84.8, m: ≈2^14.0, β: 321, d: 32737, ↻: 1, ζ: 12, tag: dual_hybrid
{'usvp': rop: ≈2^93.7, red: ≈2^93.7, δ: 1.004628, β: 321, d: 31988, tag: usvp, 
'dual_hybrid': rop: ≈2^93.7, mem: ≈2^84.8, m: ≈2^14.0, β: 321, d: 32737, ↻: 1, ζ: 12, tag: dual_hybrid}

sage: LWE.estimate(params, red_cost_model=RC.BDGL16, deny_list=["bkw", "bdd_hybrid", "bdd_mitm_hybrid", "dual_mitm_hybrid", "arora-gb"],jobs = 64)
usvp:: rop: ≈2^128.1, red: ≈2^128.1, δ: 1.004628, β: 321, d: 31988, tag: usvp                                                                                                             
bdd:: rop: ≈2^128.0, red: ≈2^127.8, svp: ≈2^125.0, β: 320, η: 372, d: 32530, tag: bdd                                                                                                    
dual:: rop: ≈2^128.4, mem: ≈2^41.9, m: ≈2^14.0, β: 322, d: 32783, ↻: 1, tag: dual           
dual_hybrid:: rop: ≈2^128.1, mem: ≈2^113.0, m: ≈2^14.0, β: 321, d: 32703, ↻: 1, ζ: 46, tag: dual_hybrid

The parameters we currently use in homomorphic encryption standards aligns with the output of LWE.estimate (which is similar to the output of the previous lwe-estimator estimate_lwe function with only slight variation in the work factors as pointed earlier)

[sararv22]

Also, can you post some smaller scale examples that behave similarly but not quite so slowly? Easier to play with those. Say, n=1024, 2048 …

The errors messages are displayed for dimension larger than or equal to 2^15. We observe the same error messages in #74 for 2^16 and 2^17 as well.

The timings for dimension starting from n = 512 are as follows without any errors for all attacks:

LWE.Parameters(n=2^13, q=2^228, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)) - 4 hours
LWE.Parameters(n=2^12, q=2^109, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)) - 1 hour
LWE.Parameters(n=2^11, q=2^54, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)) - 15 mins
LWE.Parameters(n=2^10, q=2^27, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)) - 2 mins
LWE.Parameters(n=2^9, q=2^14, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)) - less than a minute

[malb]

re work-factor: note that the blocksizes are all essentially the same and those fundamentally account for the work factor. The work factor difference is purely down to what cost model to use then for lattice reduction.

[malb]

So this is an okay-ish approximation:

params = LWE.Parameters(n=2^11, q=2^54, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19))
costs = LWE.estimate.rough(params)
beta = min(cost["beta"] for cost in costs.values())
RC.BDGL16(beta, d=2*params.n).log(2.)

[sararv22]

So this is an okay-ish approximation:

params = LWE.Parameters(n=2^11, q=2^54, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19))
costs = LWE.estimate.rough(params)
beta = min(cost["beta"] for cost in costs.values())
RC.BDGL16(beta, d=2*params.n).log(2.)

This runs quick but it also seems similar to calling LWE.estimate with everything other than usvp and dual_hybrid in the deny_list. Is that correct?
Does this mean that we don't need to consider work factor estimates for bdd or bdd_hybrid in this case? and the decoding attack estimates are the ones that are expected to take the longest time to run? Also, the error messages in #74 appear with LWE.estimate.rough as well for dimension larger than or equal to 2^15.

[malb]

bdd will only offer a "small" improvement over usvp but it's harder to bound bdd_hybrid, so no promises.

[malb]

Running

from estimator import *
params = LWE.Parameters(n=2^10, q=2^27, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19))
%prun _ = LWE.estimate(params, red_cost_model=RC.BDGL16, deny_list=["bkw", "arora-gb"], red_shape_model="gsa")

reveals some good target for performance optimisation.

         32026864 function calls (31981579 primitive calls) in 65.004 seconds

   Ordered by: internal time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
      224   23.495    0.105   23.590    0.105 lwe_primal.py:257(svp_dimension)
      226   18.779    0.083   21.058    0.093 prob.py:43(<listcomp>)
   277502    4.632    0.000    6.719    0.000 prob.py:27(<genexpr>)

[malb]

With the current main branch, I'm now getting:

from estimator import *
all_params = [LWE.Parameters(n=2^13, q=2^228, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)), 
              LWE.Parameters(n=2^12, q=2^109, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)),
              LWE.Parameters(n=2^11, q=2^54, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)),
              LWE.Parameters(n=2^10, q=2^27, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19)),
              LWE.Parameters(n=2^9, q=2^14, Xs=ND.Uniform(-1, 1, n), Xe=ND.DiscreteGaussian(3.19))]

for params in all_params[::-1]:
    t = cputime()
    res = LWE.estimate(params, red_cost_model=RC.BDGL16, deny_list=["bkw", "arora-gb"])
    t = cputime(t)
    print(t, params)

usvp                 :: rop: ≈2^130.9, red: ≈2^130.9, δ: 1.004382, β: 348, d: 955, tag: usvp
bdd                  :: rop: ≈2^126.5, red: ≈2^125.9, svp: ≈2^125.0, β: 331, η: 372, d: 915, tag: bdd
bdd_hybrid           :: rop: ≈2^126.9, red: ≈2^126.1, svp: ≈2^125.6, β: 331, η: 374, ζ: 0, |S|: 1, d: 1050, prob: 1, ↻: 1, tag: hybrid
bdd_mitm_hybrid      :: rop: ≈2^181.8, red: ≈2^181.0, svp: ≈2^180.7, β: 351, η: 2, ζ: 141, |S|: ≈2^223.5, d: 930, prob: ≈2^-47.0, ↻: ≈2^49.2, tag: hybrid
dual                 :: rop: ≈2^135.7, mem: ≈2^74.0, m: 492, β: 364, d: 1004, ↻: 1, tag: dual
dual_hybrid          :: rop: ≈2^128.0, mem: ≈2^124.8, m: 467, β: 337, d: 944, ↻: 1, ζ: 35, tag: dual_hybrid
10.467283 LWEParameters(n=512, q=16384, Xs=D(σ=0.82), Xe=D(σ=3.19), m=+Infinity, tag=None)
usvp                 :: rop: ≈2^131.6, red: ≈2^131.6, δ: 1.004391, β: 347, d: 1943, tag: usvp
bdd                  :: rop: ≈2^129.2, red: ≈2^129.0, svp: ≈2^126.2, β: 338, η: 376, d: 1934, tag: bdd
bdd_hybrid           :: rop: ≈2^129.3, red: ≈2^129.1, svp: ≈2^126.5, β: 338, η: 377, ζ: 0, |S|: 1, d: 2074, prob: 1, ↻: 1, tag: hybrid
bdd_mitm_hybrid      :: rop: ≈2^184.3, red: ≈2^183.5, svp: ≈2^183.1, β: 347, η: 2, ζ: 138, |S|: ≈2^218.7, d: 1955, prob: ≈2^-49.6, ↻: ≈2^51.9, tag: hybrid
dual                 :: rop: ≈2^134.0, mem: ≈2^72.0, m: 1006, β: 355, d: 2030, ↻: 1, tag: dual
dual_hybrid          :: rop: ≈2^130.0, mem: ≈2^124.3, m: 979, β: 341, d: 1969, ↻: 1, ζ: 34, tag: dual_hybrid
20.080671000000002 LWEParameters(n=1024, q=134217728, Xs=D(σ=0.82), Xe=D(σ=3.19), m=+Infinity, tag=None)
usvp                 :: rop: ≈2^129.7, red: ≈2^129.7, δ: 1.004479, β: 337, d: 3927, tag: usvp
bdd                  :: rop: ≈2^128.4, red: ≈2^128.3, svp: ≈2^124.7, β: 332, η: 371, d: 3972, tag: bdd
bdd_hybrid           :: rop: ≈2^128.5, red: ≈2^128.4, svp: ≈2^125.0, β: 332, η: 372, ζ: 0, |S|: 1, d: 4122, prob: 1, ↻: 1, tag: hybrid
bdd_mitm_hybrid      :: rop: ≈2^181.4, red: ≈2^180.6, svp: ≈2^180.2, β: 337, η: 2, ζ: 133, |S|: ≈2^210.8, d: 4010, prob: ≈2^-48.6, ↻: ≈2^50.8, tag: hybrid
dual                 :: rop: ≈2^131.0, mem: ≈2^68.0, m: 2034, β: 341, d: 4082, ↻: 1, tag: dual
dual_hybrid          :: rop: ≈2^128.9, mem: ≈2^120.0, m: 2006, β: 334, d: 4022, ↻: 1, ζ: 32, tag: dual_hybrid
44.494386999999996 LWEParameters(n=2048, q=18014398509481984, Xs=D(σ=0.82), Xe=D(σ=3.19), m=+Infinity, tag=None)
usvp                 :: rop: ≈2^127.9, red: ≈2^127.9, δ: 1.004571, β: 327, d: 8005, tag: usvp
bdd                  :: rop: ≈2^127.3, red: ≈2^127.3, svp: ≈2^121.8, β: 325, η: 361, d: 7955, tag: bdd
bdd_hybrid           :: rop: ≈2^127.3, red: ≈2^127.3, svp: ≈2^120.6, β: 325, η: 357, ζ: 0, |S|: 1, d: 8222, prob: 1, ↻: 1, tag: hybrid
bdd_mitm_hybrid      :: rop: ≈2^179.6, red: ≈2^178.8, svp: ≈2^178.3, β: 327, η: 2, ζ: 128, |S|: ≈2^202.9, d: 8111, prob: ≈2^-48.7, ↻: ≈2^50.9, tag: hybrid
dual                 :: rop: ≈2^128.5, mem: ≈2^66.0, m: ≈2^12.0, β: 329, d: 8180, ↻: 1, tag: dual
dual_hybrid          :: rop: ≈2^127.6, mem: ≈2^114.7, m: ≈2^12.0, β: 326, d: 8123, ↻: 1, ζ: 32, tag: dual_hybrid
84.48662299999998 LWEParameters(n=4096, q=649037107316853453566312041152512, Xs=D(σ=0.82), Xe=D(σ=3.19), m=+Infinity, tag=None)
usvp                 :: rop: ≈2^122.1, red: ≈2^122.1, δ: 1.004800, β: 304, d: 15728, tag: usvp
bdd                  :: rop: ≈2^121.7, red: ≈2^121.6, svp: ≈2^118.3, β: 302, η: 349, d: 16225, tag: bdd
bdd_hybrid           :: rop: ≈2^121.7, red: ≈2^121.6, svp: ≈2^118.3, β: 302, η: 349, ζ: 0, |S|: 1, d: 16409, prob: 1, ↻: 1, tag: hybrid
bdd_mitm_hybrid      :: rop: ≈2^175.2, red: ≈2^174.4, svp: ≈2^174.0, β: 303, η: 2, ζ: 118, |S|: ≈2^187.0, d: 16309, prob: ≈2^-50.3, ↻: ≈2^52.5, tag: hybrid
dual                 :: rop: ≈2^122.5, mem: ≈2^48.2, m: ≈2^13.0, β: 305, d: 16390, ↻: 1, tag: dual
dual_hybrid          :: rop: ≈2^121.9, mem: ≈2^107.6, m: ≈2^13.0, β: 303, d: 16323, ↻: 1, ζ: 32, tag: dual_hybrid
226.712277 LWEParameters(n=8192, q=431359146674410236714672241392314090778194310760649159697657763987456, Xs=D(σ=0.82), Xe=D(σ=3.19), m=+Infinity, tag=None)

[malb]

For the two examples on top:

from estimator import *
params = LWE.Parameters(n=2^14, q=2^438, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
%time _ = 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)

usvp                 :: rop: ≈2^128.1, red: ≈2^128.1, δ: 1.004628, β: 321, d: 31988, tag: usvp
bdd                  :: rop: ≈2^128.0, red: ≈2^127.8, svp: ≈2^125.0, β: 320, η: 372, d: 32530, tag: bdd
dual                 :: rop: ≈2^128.4, mem: ≈2^41.9, m: ≈2^14.0, β: 322, d: 32783, ↻: 1, tag: dual
CPU times: user 5.36 ms, sys: 308 ms, total: 313 ms
Wall time: 1min 21s

from estimator import *
params = LWE.Parameters(n=2^15, q=2^881, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
%time _ = 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)

usvp                 :: rop: ≈2^128.2, red: ≈2^128.2, δ: 1.004657, β: 318, d: 63223, tag: usvp
bdd                  :: rop: ≈2^128.1, red: ≈2^128.0, svp: ≈2^124.7, β: 317, η: 371, d: 65241, tag: bdd
dual                 :: rop: ≈2^128.3, mem: ≈2^41.6, m: ≈2^15.0, β: 318, d: 65551, ↻: 1, tag: dual
CPU times: user 28.9 ms, sys: 320 ms, total: 349 ms
Wall time: 6min 13s

So I think this can be marked as resolved?

[sararv22]

For the two examples on top:

from estimator import *
params = LWE.Parameters(n=2^14, q=2^438, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
%time _ = 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)

usvp                 :: rop: ≈2^128.1, red: ≈2^128.1, δ: 1.004628, β: 321, d: 31988, tag: usvp
bdd                  :: rop: ≈2^128.0, red: ≈2^127.8, svp: ≈2^125.0, β: 320, η: 372, d: 32530, tag: bdd
dual                 :: rop: ≈2^128.4, mem: ≈2^41.9, m: ≈2^14.0, β: 322, d: 32783, ↻: 1, tag: dual
CPU times: user 5.36 ms, sys: 308 ms, total: 313 ms
Wall time: 1min 21s

from estimator import *
params = LWE.Parameters(n=2^15, q=2^881, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
%time _ = 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)

usvp                 :: rop: ≈2^128.2, red: ≈2^128.2, δ: 1.004657, β: 318, d: 63223, tag: usvp
bdd                  :: rop: ≈2^128.1, red: ≈2^128.0, svp: ≈2^124.7, β: 317, η: 371, d: 65241, tag: bdd
dual                 :: rop: ≈2^128.3, mem: ≈2^41.6, m: ≈2^15.0, β: 318, d: 65551, ↻: 1, tag: dual
CPU times: user 28.9 ms, sys: 320 ms, total: 349 ms
Wall time: 6min 13s

So I think this can be marked as resolved?

It is faster now, runs for 2^16 in 37 mins without the hybrid attacks. But for 2^17, there is an error message displayed -

params = LWE.Parameters(n=2^17, q=2^2438, Xs = ND.Uniform(-1,1,n), Xe=ND.DiscreteGaussian(3.19))
%time _ = 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)                                
Algorithm functools.partial(<function primal_bdd at 0x7fd1f462f1f0>, red_cost_model=<estimator.reduction.BDGL16 object at 0x7fd1f4706f40>, red_shape_model='gsa') on LWEParameters(n=131072, q=81494711902125716134655777861999491875599538632224628068148400369915679611492280385737549950959857685191269104590170609181849573110071155272891182034899915025983391609012921934820497630841218890178037878064226527963351012247959505821882545532856740692471547139698426518063105635428261832183861090544710819611901585041432920704410399321854585122416377141479502892302012812990112903515193747406477490273959508593401124513555342908731123958682341514322306199389258369646102048096778647847193552422560834190180904234473774068922313487523460318988436744822880214340534905817686088682368271916330660823011533412782926779380492099016407021287618592387555511850507371721521048477719268512107808010477461838501261465204385223455151266876882944, Xs=D(σ=0.82), Xe=D(σ=3.19), m=+Infinity, tag=None) failed with math domain error
usvp                 :: rop: ≈2^194.8, red: ≈2^194.8, δ: 1.003226, β: 539, d: 256091, tag: usvp
dual                 :: rop: ≈2^194.8, mem: ≈2^60.0, m: ≈2^17.0, β: 539, d: 262135, ↻: 1, tag: dual
CPU times: user 32.2 ms, sys: 289 ms, total: 321 ms
Wall time: 5min 48s