# Why RLWE is hard or even has a solution?

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$$.

• "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... Sep 22, 2021 at 20:24
• @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$. Sep 22, 2021 at 20:43
• @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$ Sep 22, 2021 at 20:45
• Yes, it is equivalant to finding $s$ such that $b \approx a \cdot s$. Why do you think that is easy? Sep 22, 2021 at 20:45
• @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? Sep 22, 2021 at 20:49

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.