# 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

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.