estimator.primal_usvp

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

Estimate cost of solving LWE using primal attack (uSVP version)

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

EXAMPLES:

sage: from estimator import primal_usvp, Param, BKZ
sage: n, alpha, q = Param.Regev(256)

sage: primal_usvp(n, alpha, q)
            rop:  2^158.6
            red:  2^158.6
        delta_0: 1.005374
           beta:      257
              d:      704
              m:      447

sage: primal_usvp(n, alpha, q, secret_distribution=True, m=n)
            rop:  2^208.1
            red:  2^208.1
        delta_0: 1.004628
           beta:      321
              d:      513
              m:      256

sage: primal_usvp(n, alpha, q, secret_distribution=False, m=2*n)
            rop:  2^208.1
            red:  2^208.1
        delta_0: 1.004628
           beta:      321
              d:      513
              m:      512

sage: primal_usvp(n, alpha, q, reduction_cost_model=BKZ.sieve)
        rop:  2^103.9
        red:  2^103.9
    delta_0: 1.005374
       beta:      257
          d:      704
          m:      447

sage: primal_usvp(n, alpha, q)
            rop:  2^158.6
            red:  2^158.6
        delta_0: 1.005374
           beta:      257
              d:      704
              m:      447

sage: primal_usvp(n, alpha, q, secret_distribution=(-1,1), m=n)
            rop:   2^88.5
            red:   2^88.5
        delta_0: 1.007317
           beta:      156
              d:      492
              m:      235

sage: primal_usvp(n, alpha, q, secret_distribution=((-1,1), 64))
            rop:   2^80.0
            red:   2^80.0
        delta_0: 1.007723
           beta:      142
              d:      461
              m:      204
[USENIX:ADPS16]Alkim, E., Léo Ducas, Thomas Pöppelmann, & Schwabe, P. (2015). Post-quantum key exchange - a new hope.
[BaiGal14]Bai, S., & Galbraith, S. D. (2014). Lattice decoding attacks on binary LWE. In W. Susilo, & Y. Mu, ACISP 14 (pp. 322–337). : Springer, Heidelberg.