# estimator.drop_and_solve¶

estimator.drop_and_solve(f, n, alpha, q, secret_distribution=True, success_probability=0.99, postprocess=True, decision=True, rotations=False, **kwds)[source]

Solve instances of dimension n-k with increasing k using f and pick parameters such that cost is minimised.

Parameters: f – attack estimate function n – LWE dimension n > 0 alpha – noise rate 0 ≤ α < 1, noise will have standard deviation αq/sqrt{2π} q – modulus 0 < q secret_distribution – distribution of secret, see module level documentation for details success_probability – targeted success probability < 1 postprocess – check against shifted distributions decision – the underlying algorithm solves the decision version or not

EXAMPLE:

sage: from estimator import drop_and_solve, dual_scale, primal_usvp, partial
sage: q = next_prime(2^30)
sage: n, alpha = 512, 8/q
sage: primald = partial(drop_and_solve, primal_usvp)
sage: duald = partial(drop_and_solve, dual_scale)

sage: duald(n, alpha, q, secret_distribution=((-1,1), 64))
rop:   2^55.7
m:      478
red:   2^55.1
delta_0: 1.009807
beta:       89
repeat:   2^14.2
d:      920
c:    8.387
k:       70
postprocess:        8

sage: duald(n, alpha, q, secret_distribution=((-3,3), 64))
rop:   2^59.6
m:      517
red:   2^59.5
delta_0: 1.009403
beta:       97
repeat:   2^18.2
d:      969
c:    3.926
k:       60
postprocess:        6

sage: kwds = {"use_lll":False, "postprocess":False}
sage: duald(n, alpha, q, secret_distribution=((-1,1), 64), **kwds)
rop:   2^69.8
m:      521
red:   2^69.8
delta_0: 1.008953
beta:      107
repeat:      257
d:     1033
c:    9.027
k:        0
postprocess:        0

sage: duald(n, alpha, q, secret_distribution=((-3,3), 64), **kwds)
rop:   2^74.5
m:      560
red:   2^74.5
delta_0: 1.008668
beta:      114
repeat:  524.610
d:     1068
c:    4.162
k:        4
postprocess:        0

sage: duald(n, alpha, q, secret_distribution=((-3,3), 64), rotations=True, **kwds)
Traceback (most recent call last):
...
ValueError: Rotations are only support as part of the primal-usvp attack on NTRU.

sage: primald(n, alpha, q, secret_distribution=((-3,3), 64), rotations=True, **kwds)
rop:   2^51.1
red:   2^51.1
delta_0: 1.010046
beta:       84
d:      914
m:      445
repeat: 1.509286
k:       44
postprocess:        0

sage: primald(n, alpha, q, secret_distribution=((-3,3), 64), rotations=False, **kwds)
rop:   2^58.0
red:   2^58.0
delta_0: 1.009350
beta:       98
d:     1003
m:      494
repeat: 1.708828
k:        4
postprocess:        0


This function is based on:

 [Albrecht17] Albrecht, M. R. (2017). On dual lattice attacks against small-secret LWE and parameter choices in helib and SEAL. In J. Coron, & J. B. Nielsen, EUROCRYPT 2017, Part II (pp. 103–129).