estimator.dual_scale

estimator.dual_scale(n, alpha, q, secret_distribution, m=<Mock name='mock()' id='139938827128976'>, success_probability=0.99, reduction_cost_model=<function CheNgu12>, c=None, use_lll=True)[source]

Estimate cost of solving LWE by finding small (y,x/c) such that y ⋅ A ≡ c ⋅ x mod q as described in [EC:Abrecht17]

Parameters:
  • 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
  • m – number of LWE samples m > 0
  • success_probability – targeted success probability < 1
  • reduction_cost_model – cost model for lattice reduction
  • c – explicit constant c
  • use_lll – use LLL calls to produce more small vectors

EXAMPLES:

sage: from estimator import Param, dual_scale

sage: dual_scale(*Param.Regev(256), secret_distribution=(-1,1))
        rop:  2^105.4
          m:      286
        red:  2^105.4
    delta_0: 1.006698
       beta:      181
     repeat:   2^69.0
          d:      542
          c:   31.271

sage: dual_scale(*Param.Regev(256), secret_distribution=(-1,1), m=200)
        rop:  2^109.7
          m:      200
        red:  2^109.7
    delta_0: 1.006543
       beta:      188
     repeat:   2^74.0
          d:      456
          c:   31.271

sage: dual_scale(*Param.Regev(256), secret_distribution=((-1,1), 64))
        rop:   2^96.4
          m:      257
        red:   2^96.4
    delta_0: 1.006998
       beta:      168
     repeat:   2^59.0
          d:      513
          c:   51.065
[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).