lattice-estimator

lattice-estimator copied to clipboard

The estimator crashes (i.e. causes a Python error that takes down Sage) for some large values of q.

I’ve done some testing and it seems to be that this happens when n = 4096 and q > 2^75+2^72 — which first made us think there was a memory overflow somewhere, but then it works again for q > 2^83-2^82 and up. The issue doesn't appear for n = 8192 or n = 2048.

Example queries that go wrong:

LWE.estimate.rough(LWE.Parameters(n=4096, q=2^80, Xs=ND.SparseTernary(100,25,25), Xe=ND.SparseTernary(100,25,25)))
LWE.estimate.rough(LWE.Parameters(n=4096, q=2^80, Xs=ND.CenteredBinomial(4), Xe=ND.CenteredBinomial(4)))

I can consistently reproduce the issue both on a Linux machine (with Python 3.10.5 and Sage 9.5) and locally on my MacBook (with Python 3.10.3 and Sage 9.6). The issue also appears with the “non-rough” variant I believe, but I’m not 100% sure — I’m trying to reproduce that now but the queries take half a day to run.

Hi @BorBorBor, thank you for letting us know about this!

Initial investigations suggest that this is associated to the LWE.dual_hybrid() function, we will look into it.

In the meantime, you could use LWE.primal_usvp() and LWE.dual() to generate a rough security estimate, e.g:

sage: from estimator import *
sage: params = LWE.Parameters(n=4096, q=2^80, Xs=ND.SparseTernary(100,25,25), Xe=ND.SparseTernary(100,25,25))
sage: LWE.primal_usvp(params)
rop: ≈2^170.3, red: ≈2^170.3, δ: 1.003463, β: 488, d: 7884, tag: usvp
sage: LWE.dual(params)
rop: ≈2^172.0, mem: ≈2^103.0, m: ≈2^12.0, β: 491, d: 8123, ↻: 1, tag: dual

Oh, wow, when you say "crash" you really mean it. That's new!

Hi @bencrts, thanks! That's helpful, then we can at least continue with this project for now.

Looks like we are failing an MPFR assertion. I recieved this:

get_z_exp.c:60: MPFR assertion failed: fn <= 2147483647

as output for the first set of parameters listed in the issue. I've tracked it back to here (the filename changed to get_z_2exp.c in an update one month ago). Still trying to track where the issue occurs in the code, but it's a start.

Hi @bencrts! I understand that this isn't a priority but I was just wondering if you managed to find out anything more. We're doing some unconventional RLWE stuff (if you hadn't guessed from the premise of this post 😅) so we would really like to know what arora-gb does. For the largest numbers we are able to run without crashes, computing gröbner bases seems to be a lot more efficient than the other attacks.

Is arora_gb crashing here, i.e. what happens when you call LWE.arora_gb(params)?

Yes you're right, that one does work! It's LWE.dual_hybrid() that seems to be the problem.

HI @BorBorBor! I have taken another look at this and it appears to be a problem with the exhaustive search solver which is used as part of the hybrid-dual process. In particular, the estimate:

from estimator import *
LWE.Parameters(n=4096, q=2^80, Xs=ND.SparseTernary(100,25,25), Xe=ND.SparseTernary(100,25,25))
lwe_dual.DualHybrid.cost(params = params, solver = LWE.exhaustive_search, beta = 288)

is crashing because the exhaustive search solver is being given a 0-dimensional LWE instance, and doesn't know what to do with it. Whilst I figure out a fix for this, you could call the dual hybrid-attack seperately. To retrieve all estimates (aside from the hybrid-dual attack), you could do:

from estimator import *
params = LWE.Parameters(n=4096, q=2^80, Xs=ND.SparseTernary(100,25,25), Xe=ND.SparseTernary(100,25,25))
LWE.estimate(params, deny_list = {"dual_hybrid"})

To seperately call the hybrid-dual attack, turn off the crashing exhaustive search solver and use mitm instead:

from estimator import *
params = LWE.Parameters(n=4096, q=2^80, Xs=ND.SparseTernary(100,25,25), Xe=ND.SparseTernary(100,25,25))
LWE.dual_hybrid(params, mitm_optimization = True)

This will give you a full suite of estimates in the meantime. For the LWE.dual_hybrid() call I am getting:

rop: ≈2^191.3, mem: ≈2^180.3, m: ≈2^12.1, k: 109, ↻: 1, β: 560, d: 8399, ζ: 110, tag: dual_mitm_hybrid

I hope this helps for now!

An interesting side issue found during debugging so far is that Xs=ND.SparseTernary(100,25,25) returns False on is_sparse since the density of this secret distribution is 0.5. @malb should we figure out some way to stop this from happening, e.g. enforce that Xs=ND.SparseTernary(n, p, m) can only be called when 2 * (p + m) < n? Seems like it could lead to some issues in the code since we branch on is_sparse a lot (although it is not causing an issue here).

I guess it could also make sense for us to tie the value of Xs.n to the value of params.n in some way, so that the input in this case would need to be Xs=ND.SparseTernary(4096, 1024, 1024) although this is probably less important.

If we throw a ValueError here do we gain anything? That is, if the user then does the right thing and produces a dense distribution, it'd still return False on is_sparse as expected?

Created #52 with an example regarding the is_sparse thing, not sure if it warrants a fix but I guess we can discuss there.

With regards to this one, I added a branch to this issue (here) with a hacky-fix, running tests now and will create a PR if everything passes.