I want to use lwe estimator to find classical and quantum security of my proposed key exchange protocol. On this website, I want to understand the output of sage code on lwe estimator given bellow.

sage: load("estimator.py")

sage: n, alpha, q = Param.Regev(128)

sage: costs = estimate_lwe(n, alpha, q)

The output is

usvp: rop: ≈2^57.2, red: ≈2^57.2, δ_0: 1.009214, β: 101, d: 349, m: 220

dec: rop: ≈2^61.5, m: 229, red: ≈2^61.5, δ_0: 1.009595, β: 93, d: 357, babai: ≈2^46.8, babai_op: ≈2^61.9, repeat: 293, ε: 0.015625

dual: rop: ≈2^81.4, m: 376, red: ≈2^81.4, δ_0: 1.008810, β: 111, d: 376, |v|: 736.521, repeat: ≈2^19.0, ε: 0.003906

What is rop, red, δ_0, β, d, m stands for in the output. I search many official documentation of lwe estimator like this (they give brief description of other parameters like bop in section 7) and this. But they provide information about input parameters and algorithms used and not about the output parameters. Any help is appreciated.


3 Answers 3

  • δ_0: the root Hermite factor required
  • β: the BKZ block size
  • d: the dimension of the lattice being reduced
  • m: the number of LWE samples used
  • $\begingroup$ Thanks for replying. Can you please also tell about rop, red, repeat, \epilson and |v|. So, that I will accept your answer. $\endgroup$
    – vivek
    Commented Feb 24, 2020 at 5:37
  • $\begingroup$ Also, please tell the difference between bop and rop? Thanks. $\endgroup$
    – vivek
    Commented Feb 24, 2020 at 5:38

I want to use lwe estimator too. But same as you, I can't find any explainations about this. So I search the source code. The most important fuction is lattice_reduction_cost() tell you the cost for lattice_reduction.

def lattice_reduction_cost(cost_model, delta_0, d, B=None):
Return cost dictionary for returning vector of norm` δ_0^d Vol(Λ)^{1/d}` using provided lattice
reduction algorithm.

:param lattice_reduction_estimate:
:param delta_0: root-Hermite factor `δ_0 > 1`
:param d: lattice dimension
:param B: bit-size of entries

beta = betaf(delta_0)
cost = cost_model(beta, d, B)
return Cost([("rop", cost), ("red", cost), ("delta_0", delta_0), ("beta", beta)])

And the default cost_model is reduction_default_cost = BKZ.enum.It's definition is in class BKZ.

Have you got some explainations about this question? @vivek. Hope the author provides more READMEs to the lwe estimator, [email protected]

  • 1
    $\begingroup$ Welcome to Cryptography. Part of your answer is rather a comment that you cannot make yet due to reputation. Let see how our moderators can handle this. $\endgroup$
    – kelalaka
    Commented Jun 17, 2020 at 17:15
  • $\begingroup$ @weizhengxing No complete answer. MartinR.Albrecht is creator of this tool, hope he gives some details. But I will you refer you to an article where you get some idea to use LWE estimator. The link of the article is ieeexplore.ieee.org/abstract/document/8300634 $\endgroup$
    – vivek
    Commented Jun 18, 2020 at 11:04
  • $\begingroup$ @vivek thanks for this $\endgroup$ Commented Jun 20, 2020 at 5:15

A full description of the parameters is in the documentation.. Each parameter is related to a specific attack such as Dual, Primal and so on.

In summary :

rop: Total number of word operations (≈ CPU cycles).

mem: Total amount of memory used by solver (in elements mod q).

red: Number of word operations in lattice reduction.

β: BKZ block size.

ζ: Number of guessed coordinates.

h1: Number of non-zero components among guessed coordinates (if secret distribution is sparse)

prob: Probability of success in guessing.

repetitions: How often we are required to repeat the attack.

d: Lattice dimension.

t: Number of secrets to guess mod 2 (only if fft is True)


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.