Score:1

RLWE with invertible elements

cn flag

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?

Score:1
ng flag

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.

a196884 avatar
cn flag
Great answer - thanks!
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.