Score:1

Why RLWE is hard or even has a solution?

cn flag

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

poncho avatar
my flag
"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...
Paprika avatar
cn flag
@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$.
Paprika avatar
cn flag
@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$
poncho avatar
my flag
Yes, it is equivalant to finding $s$ such that $b \approx a \cdot s$. Why do you think that is easy?
Paprika avatar
cn flag
@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?
Score:4
ng flag

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.

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.