Score:1

Security level of FHE constructions for non-standard parameters

es flag

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?

Daniel avatar
ru flag
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.
Maarten Bodewes avatar
in flag
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.
Score:2
us flag

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.

muhammad haris avatar
es flag
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
Hilder Vitor Lima Pereira avatar
us flag
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.
muhammad haris avatar
es flag
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
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.