lattice-estimator icon indicating copy to clipboard operation
lattice-estimator copied to clipboard

"Jumps" in estimates based on is_sparse

Open bencrts opened this issue 3 years ago • 0 comments

We call different costing functions for very similar parameter sets which could lead to "jumps". For example, for the two parameter sets:

sage: params = LWE.Parameters(n=1024, q=2^20, Xs=ND.SparseTernary(512,128,128), Xe=ND.DiscreteGaussian(3.2))
sage: params_is_sparse = LWE.Parameters(n=1024, q=2^20, Xs=ND.SparseTernary(512,128,127), Xe=ND.DiscreteGaussian(3.2))

we would see a 5-bit difference:

sage: LWE.dual_hybrid(params)
rop: ≈2^172.9, mem: ≈2^167.8, m: 911, β: 502, d: 1890, ↻: 1, ζ: 45, tag: dual_hybrid
sage: LWE.dual_hybrid(params_is_sparse)
rop: ≈2^178.0, mem: ≈2^168.8, m: 909, β: 501, d: 1886, ↻: 41, ζ: 47, h1: 22, tag: dual_hybrid

since different costing functions are called based on the result of is_sparse.

bencrts avatar Oct 20 '22 12:10 bencrts