# Why is the error in RLWE "smaller" than LWE?

In LWE, the standard deviation satisfies $$\alpha p > 2\sqrt{n}$$, when we consider the discrete LWE in $$\mathbb{Z}_p$$, then the rounded Gaussian has standard deviation $$\alpha p$$. But in RLWE, the error has standard deviation $$\sigma = 3.2$$, it seems too small on the analogy of LWE.

Is it related to the fact "In RLWE, the ring $$R^{\vee} = mR$$" ?

• Where are you seeing that $\sigma=3.2$ for RLWE? That sounds like a specific choice someone made for concrete parameters, in contrast to $\alpha p > 2\sqrt{n}$ from the worst-case-hardness theorems for LWE. Jun 3 at 11:37
• In homomorphic encryption standard. What I'm trying to say is: the RLWE is defined as $R_q \times R_q^\vee$, when we transform the $R_q^\vee$ to $R_q$, it will generate a factor $n$(n is the same as the $x^n+1$), so when we generate the RLWE error in $R_q$, whether we can generate a smaller error $e$ and this $e$ corresponds to an $e' = n\dot e$ in $R_q^\vee$ Jun 4 at 1:37
• Both things you write are true but they aren’t really connected. The standard uses a much narrower error than what the worst-case-hardness theorems require. This is the case even after we account for “rescaling” $R^\vee$ to $R$. Jun 4 at 2:00

1. Parameters based on cryptanalysis of $$SIVP_\gamma$$ and worst-case to average-case reductions
The first is somewhat non-trivial (and requires more than just setting $$\sigma > 2\sqrt{n}$$) due to the known tightness gaps of the worst-case to average-case reductions. If one tries to concretely (in the notion of concrete security) analyze these reductions, one gets a statement of the form (from page 16):
Thus, if average-case DLWE can be solved in time $$T$$, then Theorem 1 shows that $$SIVP_\gamma$$ can be solved by a quantum algorithm in time $$2^{504}T$$.
One can still set parameters to be concretely secure under the hardness of worst-case lattice problems. This masters thesis computes some parameters on page 28 --- one particular parameter set is $$n = 1870, q\approx 2^{22}, \sigma = 17.5$$ for a concrete estimate of 128-bit security using estimates for solving $$SIVP_\gamma$$ and the worst-case to average-case security reduction.
Note that these parameters are a good deal larger than parameters supported by cryptanalysis --- the plain LWE NIST PQC third round alternate FrodoKEM sets parameters as $$n = 640, q\approx 2^{15}, \sigma = 2.8$$ for 128 bits of security. This is to say that the indirection (of using a concrete estimate to solve $$SIVP_\gamma$$, and then apply a worst-case to average-case security reduction, vs. just using a concrete estimate to solve LWE) leads to less efficient constructions, so in practice is not used often.