homomorphicencryption standards already provide recommended parameters and their corresponding security levels. However, I would like to calculate a security level for nonstandard parameter selection.

Is there an simple way to calculate the security level?

  • $\begingroup$ I don't think you should do that if you're planning on actually using your parameter selection. In general, these estimates come from a vast and complex body of research on lattice-based cryptography. There are many parameters involved as you may know (noise, deviation, dimension, etc.) and the truth is that only a handful of people know their relations and concrete sizes. The homomorphic encryption standardization is precisely an effort to take this knowledge to a more general public, for a concrete set of parameters. $\endgroup$
    – Daniel
    Sep 15 at 1:52
  • $\begingroup$ While I agree that this would be useful, that doesn't mean that there shouldn't be a well defined method of deriving at those numbers for those who want to check them. That said, the question asks for a simple way. If there isn't such a thing (or a likewise loosely correct one) then yeah, the question may have a negative result. $\endgroup$
    – Maarten Bodewes
    Sep 15 at 11:57

The standard way is by using the LWE estimator (if it is simple or not it is debatable).

It estimates the cost of known attacks against LWE instances given parameters $n$, $\alpha$, and $q$, where $\alpha$ represents the noise ratio and can be obtained from the parameter $\sigma$ from the discrete Gaussian using the formula $\alpha = \sqrt{2 \pi} \cdot \sigma / q$, already implemented in command alpha = alphaf(sigmaf(sigma), q).

The estimator basically finds the block size $\beta$ that the BKZ algorithm will have to use to break the LWE problem. But estimating the running time of BKZ-$\beta$ is not simple, so, to get the actual security level, you have to choose a cost model for BKZ.

In short, BKZ runs on a lattice of dimension $d$ and does several calls to a SVP solver in dimension $\beta$. The SVP oracle is often assumed to require $2^{0.292\cdot \beta}$ operations in a classical computer and $2^{0.265\cdot \beta}$ in a quantum one. Thus, using reduction_cost_model=BKZ.sieve in the LWE estimator will give you the number of operations as $2^{0.292\cdot \beta + 16.4 + \log_2(8 \cdot d)}$ and you want it to be larger than $2^\lambda$ for $\lambda$ bits of security.

Some people are more conservative (paranoid?) and ignore cost related to the dimension $d$ and the many calls to the SVP oracle, therefore they estimate the number of operations of BKZ as a single call to the SVP solver, thus, they get $2^{0.292\cdot \beta}$ or $2^{0.265\cdot \beta}$. This is called the "core-SVP" cost model and it was used, for example, to estimate the security of SABER.

  • $\begingroup$ Thanks this is very helpful. I ran the estimator and got following outcome: sage: a = alphaf(sigmaf(3.2), 2^124) sage: n = 4096; q = 2^124 ; alpha = a sage: costs = estimate_lwe(n, alpha, q) usvp: rop: ≈2^161.8, red: ≈2^161.8, δ_0: 1.005117, β: 276, d: 8199, m: ≈2^12.0 .... ——————— I am not sure how to get estimate out of it, can you please guide a bit more. Thanks very much $\endgroup$ Sep 16 at 3:33
  • $\begingroup$ This is telling you that the number of operations needed by BKZ to break LWE in the unique-SVP attack is approx $2^{161.8}$, so the security level is $\lambda > 161$ (considering the other attacks printed out cost more than this). But you did not specify the cost model and I don't know which one the estimator uses by default. Also, this is probably supposing that the key is uniform in Z_q^n. It would be good to use something like estimate_lwe(n, alpha, q, secret_distribution=(0,1), reduction_cost_model=BKZ.sieve) to choose the cost model and the distribution of sk as the one you are using. $\endgroup$ Sep 16 at 7:30

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.