Score:0

Small modulus to noise ration in LWE implies better security

in flag

I don't quite understand why a smaller quotient between modulus $q$ and the noise's standard deviation implies better security against known attacks.

Ievgeni avatar
cn flag
Could you give more context about this assumption? Where did you see it?
C.S. avatar
in flag
Here: https://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.455.9719&rep=rep1&type=pdf Page 14: "A smaller modulus-to-noise ratio provides stronger concrete security against known attacks" An it is well know that smaller q implies better security
Ievgeni avatar
cn flag
"smaller ratio" and "smaller q" are not identical. I suggest you to edit your question with the good terms.
Score:2
ng flag

First, it should be clear that one can always increase the noise in an LWE instance without hurting security, so (for fixed modulus) larger modulus-to-noise ratio implies "not worse" security. Of course, this does not explain why the security should vary with respect to $\sigma/q$, instead of some more complicated expression. There are two reasons to see why this is the "right" way to measure the size of the noise.

The first is that it is what shows up in the worst-case to average-case reductions. For example, Regev's initial reduction shows that:

Theorem 1.1 (Informal) Let $n, p$ be integers and $\alpha\in(0,1)$ be such that $\alpha p >2\sqrt{n}$. If there exists an efficient algorithm that solves $LWE(p, \Psi_\alpha)$ then there exists an efficient quantum algorithm that approximates the decision version of the shortest vector problem (GAPSVP) and the shortest independent vectors problem (SIVP) to within $\tilde{O}(n/\alpha)$ in the worst case.

Note that $1/\alpha$ is the "modulus to noise" ratio, so approximation factor one has to assume is hard directly scales with $1/\alpha$. In practice one doesn't want to concretely appeal to the worst-case to average-case reductions when choosing parameters though, for two reasons:

  1. $\sigma := \alpha q > 2\sqrt{n}$ is required, so for $n> 500$ (which is a comfortable lower bound) one needs $\sigma > 40$, much larger than people use in practice.

  2. There is furthermore a "tightness gap" in the reduction, see section 6 of Another Look at Tightness 2). This only impacts "the constants" in the reduction, but the impact is quite large, and to appeal to the reduction one has to choose rather inefficient parameters.

So how can we say that concretely that smaller modulus-to-noise ratio in LWE implies better security? There are two points here:

  1. The modulus of LWE does not impact the security of it much, see for example cor 3.2 of Classical Hardness of LWE.

  2. You can explicitly parametrize known attacks in terms of the modulus-to-noise ratio, see chapter 4 of Rachel Player's Thesis, or the LWE estimator.

Note that this is the story for LWE. You have used the tag for Ring LWE as well. Things are somewhat more complex there, and can depend on the "splitting behavior" of the modulus $q$ in whatever number field you are working in, although I am the wrong person to write an answer on this topic.

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.