Security level of FHE constructions for non-standard parameters

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?

• 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. Commented Sep 15, 2021 at 1:52
• 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. Commented Sep 15, 2021 at 11:57

1 Answer

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.

• 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 Commented Sep 16, 2021 at 3:33
• 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. Commented Sep 16, 2021 at 7:30
• got it I set parameters with secret key distribution as in SEAL (I am using seal) and BKZ.sieve cost model and it gives 111 bits of security .. thanks for your answer Commented Sep 22, 2021 at 15:05