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).