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

1 Answer 1

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$
6
  • $\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
    Commented Jun 30, 2018 at 17:40
  • $\begingroup$ @Cryptostase why do you think so? $\endgroup$ Commented Jul 1, 2018 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
    Commented Jul 1, 2018 at 11:39
  • $\begingroup$ @Cryptostase so, by "not well defined" do you mean easy to solve? $\endgroup$ Commented Jul 1, 2018 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
    Commented Jul 1, 2018 at 15:33

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.