4
$\begingroup$

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

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

0

Reset to default

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.