# Is the ring learning with errors problem still hard if the errors are drawn from some subspace?

Let $R=\mathbb{Z}_p[x]/x^n+1$ be the ring used in normal RLWE, which is linear space over $\mathbb{Z}_p$ with dimension of $n$, let $S$ be a linear subspace of $R$ which described by linear independent vectors $r_1,r_2,\cdots,r_m\in R$ where $m<n$. My question is:

Let $s\overset{\$}{\leftarrow} R$, is it hard to extract$s$by given$\{(a_i,a_i*s+e_i)\}_i$where$a_i\overset{\$}{\leftarrow}R$ and $e_i\overset{\chi}{\leftarrow}S$ for some distribution $\chi$?

Or

Is the distribution $\{(a_i,a_i*s+e_i)\}_i$ computational indistinguishable with $\{(a_i,b_i)\}_i$ where $b_i\overset{\$}{\leftarrow} \text{Span}(a_i*s, S)$? You may assume$m\sim n$if necessary (it is the normal RLWE problem when$m=n$). • You might want to specify whether$r_1,\dots,r_m$are given / known to the attacker. – D.W. Jun 14, 2016 at 23:45 • Hint: is plain LWE hard if every$n$-tuple of error terms lies in a known subspace of$\mathbb{Z}^n\$? And how does this relate to your question? Jun 14, 2016 at 23:46
• @D.W. It can be known to the attacker.
– Paul
Jun 15, 2016 at 1:22