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 '16 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$ – Chris Peikert Jun 14 '16 at 23:46
  • $\begingroup$ @D.W. It can be known to the attacker. $\endgroup$ – Paul Jun 15 '16 at 1:22

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.