4
$\begingroup$

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.

Improve this question
$\endgroup$
4
$\begingroup$
  • δ_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
Improve this answer
$\endgroup$
2
  • $\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 Feb 24 '20 at 5:37
  • $\begingroup$ Also, please tell the difference between bop and rop? Thanks. $\endgroup$ – vivek Feb 24 '20 at 5:38
0
$\begingroup$

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, thanks.@MartinR.Albrecht

Improve this answer
$\endgroup$
3
  • 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 Jun 17 '20 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 Jun 18 '20 at 11:04
  • $\begingroup$ @vivek thanks for this $\endgroup$ – weizhengxing Jun 20 '20 at 5:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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