1
$\begingroup$

I was thinking about why and how the RLWE problem is hard at all. I know that it's hard because it can be reduced to the shortest vector problem, but I'm thinking about how does it even have a solution.

The problem is basically:

$a_{i}(x)$ be a set of random but known polynomials from $F_q [ x ] / Φ ( x )$ with coefficients from all of $F_q$.

$e_i ( x ) $ be a set of small random and unknown polynomials relative to a bound $b$ in the ring $F_q [ x ] / Φ ( x )$.

$s(x)$ be a small unknown polynomial relative to a bound $b$ in the ring $F_q [ x ] / Φ ( x )$.

$b_i ( x ) = ( a_i ( x ) ⋅ s ( x ) ) + e_i ( x )$

The RLWE problem consists of finding the polynomial $s$ given $b$ and $a$. But how do I know that I found it, if the error $e$ could be anything? For example, I could pick a moderate $s$ such that the result is close to $b$ and invent any $e$ such that $b = a.s + e$. Since $e$ is random and unknown, it could be anything. I don't even have a way of verifying that I found the rigth one because I don't know the $e$.

$\endgroup$
5
  • 1
    $\begingroup$ "Since $e$ is random and unknown, it could be anything"; actually, $e$ is required to be 'small' (for some definition of small); just setting it to $e = b - a \cdot s$ for some random $s$ won't satisfy the small part... $\endgroup$
    – poncho
    Sep 22, 2021 at 20:24
  • $\begingroup$ @poncho isn't this equivalent to the problem of finding $b \approx a\cdot s$? Because once I do that then I can just choose $e$. $\endgroup$
    – Paprika
    Sep 22, 2021 at 20:43
  • $\begingroup$ @poncho how do I know that I found the solution anyways? I could have find another $s$ that does not work with the original $e$ but work with my invented $e$ $\endgroup$
    – Paprika
    Sep 22, 2021 at 20:45
  • 1
    $\begingroup$ Yes, it is equivalant to finding $s$ such that $b \approx a \cdot s$. Why do you think that is easy? $\endgroup$
    – poncho
    Sep 22, 2021 at 20:45
  • $\begingroup$ @poncho so in the problem the $e$ does not have to be the one originally sampled by the secret key owner? It could be my $e$ which could or could not be different? $\endgroup$
    – Paprika
    Sep 22, 2021 at 20:49

1 Answer 1

4
$\begingroup$

There are two key points that you are mentioning (one mentioned by Poncho in the comments --- I repeat here for exposition purposes).

  1. The RLWE errors $e_i(x)$ are small, and
  2. the secret $s(x)$ is consistent across all samples.

This gives a fairly simple way to verify that you have recovered the correct $s(x)$ --- split your set of samples in half, recover $s(x)$ from half of the samples, and verify that the same $s(x)$ is such that $a(x)s(x)\approx b(x)$ (up to "small" error) on the other half of samples. On all samples you should verify that the recovered $e(x) = b(x)-a(x)s(x)$ is small. I believe this technique is known as cross-validation in statistics, but whatever it is called it works here fine as well.

There is another point to be made that, depending on the parameters chosen, with high probability you will have that the RLWE secret is itself unique (so you can prove that your worries cannot happen in the first place, upon appropriate parametrization). See for example this question for details.

$\endgroup$

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.