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


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

  • $\begingroup$ You might want to specify whether $r_1,\dots,r_m$ are given / known to the attacker. $\endgroup$
    – D.W.
    Jun 14, 2016 at 23:45
  • $\begingroup$ 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? $\endgroup$ Jun 14, 2016 at 23:46
  • $\begingroup$ @D.W. It can be known to the attacker. $\endgroup$
    – Paul
    Jun 15, 2016 at 1:22


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.