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$" ?

  • $\begingroup$ 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. $\endgroup$ Jun 3 at 11:37
  • $\begingroup$ 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$ $\endgroup$ Jun 4 at 1:37
  • $\begingroup$ 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$. $\endgroup$ Jun 4 at 2:00

This has nothing to do with LWE vs RLWE, and instead has to do with using:

  1. Parameters based on cryptanalysis of $SIVP_\gamma$ and worst-case to average-case reductions
  2. Parameters based on cryptanalysis of LWE

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.


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.