sage: sage: %time LWE.primal_bdd(schemes.SEAL22_32768.updated(n = 65536, q = 2**(2*log(schemes.SEAL22_32768.q))))
CPU times: user 36.4 s, sys: 633 ms, total: 37 s
Wall time: 37.3 s
rop: ≈2^186.3, red: ≈2^186.3, svp: ≈2^176.1, β: 531, η: 555, d: 127471, tag: bdd
The idea is that checking for the required SVP dimension from from 0 to n isn't needed, and we can check from 0 to some other value much smaller than n (arbitrarily chosen for now).
The idea here is that the number of secret co-efficients guessed, zeta, doesn't need to be checked between 0 and n and can instead be searched for in some range [0, zeta_max], where zeta_max is computed using a usvp estimate. A nice consequence of this change is that we can run hybrid attack estimates for very large values of n in a reasonable amount of time:
For BDD Before:
After:
The idea is that checking for the required SVP dimension from from
0tonisn't needed, and we can check from0to some other value much smaller thann(arbitrarily chosen for now).For Hybrid-BDD Before:
After:
The idea here is that the number of secret co-efficients guessed,
zeta, doesn't need to be checked between0andnand can instead be searched for in some range[0, zeta_max], wherezeta_maxis computed using a usvp estimate. A nice consequence of this change is that we can run hybrid attack estimates for very large values ofnin a reasonable amount of time: