Low BDD Estimate

[bencrts]

Running:

from estimator import *
D = ND.DiscreteGaussian
params = LWE.Parameters(n=256, q=18446744073709551616, Xs=D(0.50, -0.50), Xe=D(2305843009213693952.00), m=+Infinity, tag='test')
LWE.estimate(params, red_cost_model = RC.BDGL16, deny_list = ("arora-gb", "bkw"))

Gives an output of:

usvp                 :: rop: ≈2^144.9, red: ≈2^144.9, δ: 1.003726, β: 440, d: 303, tag: usvp
bdd                  :: rop: ≈2^91.7, red: ≈2^42.9, svp: ≈2^91.7, β: 40, η: 258, d: 257, tag: bdd
bdd_hybrid           :: rop: ≈2^285.9, red: ≈2^44.8, svp: ≈2^285.9, β: 40, η: 923, ζ: 0, |S|: 1, d: 941, prob: 1, ↻: 1, tag: hybrid
dual                 :: rop: ≈2^160.1, mem: ≈2^101.4, m: 66, β: 492, d: 322, ↻: 1, tag: dual
dual_hybrid          :: rop: ≈2^156.3, mem: ≈2^150.9, m: 68, β: 479, d: 310, ↻: 1, ζ: 14, tag: dual_hybrid

bdd seems very low here, a few things seem odd:

1. optimizing for β: 40
2. large guessing dimension (η: 258 which is greater than n=256)

I guess (1) and (2) are probably related.

[bencrts]

Just noticed that bdd_hybrid also optimizes for β: 40 and has a very high η in comparison to dual_hybrid, so probably an issue with cost_zeta (?)

[malb]

usvp and dual have a higher block sizes than lattice dimensions, so it's all a bit off

[malb]

I think a challenge with these parameters is that for "typical" choices of, say "beta" and "d" these aren't even uSVP instances, i.e. the norm of the target will not be unusually short.

[bencrts]

Yeah, good point, these are definitely edge-case params.

In terms of a fix, other than 8cd0c51, the only thing that comes to mind is that we could somehow bound σ/q -- and not give certain attack outputs (e.g. BDD/uSVP) when the bound is satisfied?

Dual/mitm/exhaustive-search should still be able to provide some sort-of useful output, right?(unless I'm missing something).