0
$\begingroup$

Suppose $R=\mathbb{Z}[X]/f(X)$ is a polynomial ring.

Decisional Ring-LWE is hard if one cannot distinguish the following samples:

  • $(a_i, b_i) \in R^2$ for $i\in [0,k-1]$ (completely random)

  • $(a_i, b_i=a_is+e_i) \in R^2$ for $i\in [0,k-1]$ ($b_i$ is obtained by multiplication of $a_i$ and secret $s$ masked by some noise)

This requires $k$ samples. However in homomorphic encryption scheme, key generation of public key requires just one Ring-LWE sample.

Why is this secure?

$\endgroup$
  • $\begingroup$ it's harder to get the private key with one sample than with k samples. $\endgroup$ – user27950 May 5 '18 at 15:06
  • $\begingroup$ Intuitively that is. Then, why do original papers of RLWE and LWE assume problems with many samples? $\endgroup$ – mallea May 5 '18 at 16:15
2
$\begingroup$

The security proofs on the papers about (R)LWE use several samples (usually denoted by $m$) because then the results (and the security guarantees) are stronger. And, anyway, they usually give upper bounds to $m$ (as being at most polynomially big in $n$), but not lower bounds.

For both, the decisional and the search version of the problem, giving less samples can only make the problem harder.

To see that, notice that if an attacker can distinguish the two distributions given only one sample, than it can break (R)LWE with multiple samples by just ignoring $m-1$ samples and distinguishing in the way he/she knows with one sample. And this argument works for any number of samples smaller than $m$ (so, we have a reduction from the (R)LWE problem with $m$ samples to the (R)LWE problem with any $m' < m$ samples).

To be more confident about that, take a look at section 4.1.1 of A Decade of Lattice Cryptography, where Chris Peikert explains why we can ignore columns of the SIS problem. It is basically the same argument to your case.

$\endgroup$
  • $\begingroup$ There is one important caveat here. With one sample the RLWE problem is only well defined, if the secret key is from the distribution $\chi$. $\endgroup$ – user27950 Jun 30 '18 at 17:40
  • $\begingroup$ @Cryptostase why do you think so? $\endgroup$ – Hilder Vítor Lima Pereira Jul 1 '18 at 10:28
  • $\begingroup$ let $a,b$ be a given RLWE sample. Assume a is invertible. If the secret key s can be uniformly chosen from $R$, then one can always construct a solution by chosing an arbitrary $e \in \chi$ and calculate $s = (b - e)*a^{-1}$. $\endgroup$ – user27950 Jul 1 '18 at 11:39
  • $\begingroup$ @Cryptostase so, by "not well defined" do you mean easy to solve? $\endgroup$ – Hilder Vítor Lima Pereira Jul 1 '18 at 12:16
  • $\begingroup$ Depends on your taste. I would call it "undefined", because (a,b) does not determine s uniquely. So one cannot speak about finding the s. $\endgroup$ – user27950 Jul 1 '18 at 15:33

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.