The plain, normal-form, decisional LWE problem over $\mathbb{Z}/q\mathbb{Z}$ is: given a uniformly random $n\times n$ matrix $A$ and vector $b\in \mathbb{Z}/q\mathbb{Z}^n$, decide if $b=As+e$ for small $s$ and small $e$.

The decisional ring LWE problem is, in $R_q:=\mathbb{Z}[x]/(q,p(x))$, given uniformly random $a\in R_q$ and $b\in R_q$, decide if $b=as+e$ for small $s,e$.

The intuition that LWE is at least as hard as ring LWE is that we can express the ring LWE problem as a plain LWE problem by expressing $b$, $s$, and $e$ as vectors, and $a$ as a matrix, and then it is exactly an LWE problem. $a$ produces a circulant matrix $A$, which feels like it should be easier.

But this is only a proof that ring-LWE reduces to worst-case LWE. I want a reduction to average-case LWE. The same technique does not work: circulant matrices might be the hardest type of matrix for LWE. Or at least, I can't prove otherwise.

If there were an easy random self-reducibility proof for the randomness of the matrix $A$, that would give the result. But everything I know of goes through the heavy (and non-tight!) machinery of the lattice -> LWE reductions, rather than directly LWE -> LWE.

Does such a reduction exist?


1 Answer 1


Few things: Circulant LWE is easy --- it corresponds to RLWE in $\mathbb{Z}_q[x]/(x^n-1)$, which (for $n = 2^k$) is (ring) isomorphic to $\mathbb{Z}_q[x]/(x-1)\times \prod_i \mathbb{Z}_q[x]/(x^{2^i}+1)$. In particular, one can project down onto the $\mathbb{Z}_q[x]/(x-1)$ component (corresponding to evaluation of the polynomial at 1) to reduce to a 1D plain LWE instance. To avoid this we instead work in $\mathbb{Z}_q[x]/(x^{2^{k-1}}+1)$, e.g. the largest-degree irreducible factor of $\mathbb{Z}_q[x]/(x^{2^k}-1)$, which corresponds to negacyclic (rather than cyclic matrices). In general, $\mathbb{Z}_q[x]/(f(x))$ need not have any worst-case hardness. There are some papers on this (generally with titles that include some combination of "Provably" and "Weak RLWE").

Second, my understanding is that there is a fairly straightforward way to rerandomize the $A$ component of $(A, u)$, though the technique is not sample-preserving. This is done by letting $r$ be suitably random (generally uniform in $\{0,1\}^m$, or discrete Gaussian), and outputting $(r^t A, r^t u)$. As written this only makes sense for plain LWE, but for RLWE one can instead take random linear combinations of RLWE instances. There are some nuances here (plain LWE shows $r^t A$ is uniform by the leftover hash lemma, which is false for RLWE. Instead one needs a "regularity lemma"), but is this the kind of thing you are hoping existed?

  • $\begingroup$ The re-randomization you describe also inflates the error, correct? And indeed, it's not sample preserving (LWE with 1 sample is trivially hard/easy). So we could say LWE(m,n,q,chi_e) is at least as hard as MLWE(2m,n,q,chi_e/r) for some r, depending on how to do the re-randomization, but I'm wondering if there is a reduction that matches the intuition that RLWE ought to be directly easier than the corresponding LWE instance. $\endgroup$
    – Sam Jaques
    Dec 7, 2023 at 21:33
  • $\begingroup$ Yes it does. And I doubt there is anything saying RLWE is strictly easier, as we practically use the same attacks on both at the same cost. Any "RLWE is strictly easier in general" result should (practically) mean we have better attacks, which we don't. $\endgroup$
    – Mark Schultz-Wu
    Dec 7, 2023 at 23:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.