RLWE with invertible elements

Question

Let $R = \mathcal{O}_K$ be the ring of ingtegers of $K$, where $K$ is an algebraic number field, and $q$ a modulus. Let $\chi$ be some error distribution used to sample an element $e$. A primal RLWE sample has the form $(a,a\cdot s+e)\in R_q\times R_q$. The variant which takes $a$ to be invertible has been used (e.g. here) and the variant which takes $s$ to be invertible has also been used (e.g. here). My question is:

Is RLWE secure if both $a$ and $s$ are chosen to be invertible ring elements?

Answer 1

Yes, for general reasons. Namely, $a$ being invertible is:

1. Publicly verifiable, and
2. occurs with non-negligible probability $p$ (over uniform choice of $a$), see this for details.

Whenever you have a condition like this, you can have any hypothetical adversary first check if the condition holds, and if it doesn't then "guess" the answer randomly. This reduces the advantage by a multiplicative factor $p$, but as this is non-negligible it doesn't matter (for asymptotic notions of security at least).

This is precisely the explanation that is given in the Steinfield and Stehle paper you linked, but it has nothing to do with the "base problem" they are working with being RLWE with uniform secrets, and holds in the generality I mentioned above.

Independently of the above, this is also a motivation for the worst-case to average-case reductions in lattice cryptography. Often there is some "obvious" candidate for a hard problem (factoring for example, or BDD/CVP for lattices), but pinning down the precise average-case distribution to use may be unclear. The worst-case to average-case reductions show that a number of average-case distributions for LWE problems are not "structurally bad", for example:

1. uniform $a$, uniform $s$, gaussian $e$ (of standard deviation $\geq \Omega(\sqrt{n})$, larger than most people use in practice)
2. uniform $a$, $s$ that follows the distribution of $e$

Once we know that uniform $a$ is the "right" distribution to work with, we can freely impose any "large" (meaning occurs with non-negligible probability) condition we want on $a$, including that it is invertible (or has first coordinate $1$, or has $\sum_i a_i \equiv 0 \bmod q$ for polynomially-large $q$, or essentially anything). Note that this is only true asymptotically though --- the worst-case to average-case reductions aren't particularly useful in concretely parametrizing LWE, as one can justify smaller parameters by directly cryptanalyzing LWE.