0
$\begingroup$

Consider the problem of distinguishing between polynomially many samples of either \begin{equation} (x, b, As + e) ~~\text{or}~~\left(x, b, ~Ax + b\cdot(As + e) + e'\right). \end{equation}

Here, $A$ is a public matrix and $s$ is a secret vector chosen uniformly at random. $e$ and $e'$ are Gaussian errors. $x$ and $b$ are sampled uniformly at random.

The dimensions of different objects are:

\begin{align} b &\in \{0, 1\}, \\ x &\in \mathbb{Z}_{q}^{n}, \\ s &\in \mathbb{Z}_{q}^{n}, \\ A &\in \mathbb{Z}_{q}^{m \times n}, \\ e, e' &\in \mathbb{Z}_{q}^{m}, \\ \end{align}

$q \geq 2$ is a prime integer.

Are these two cases (computationally) indistinguishable, when we are given polynomially many samples? I think they are, but I could not tie them to a conjecture.

Note that by LWE,

\begin{equation} (x, b, As + e) ~~\text{and}~~\left(x, b, u\right), \end{equation} are computationally indistinguishable and so are \begin{equation} (x, b, ~Ax + b\cdot(As + e) + e') ~~\text{and}~~\left(x, b, ~Ax + b\cdot u + e'\right). \end{equation}

$u$ is a uniformly random sample. However, I could not reduce my case to LWE.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
0
$\begingroup$

One can trivially distinguish $(x,0,u)$ from $(x,0,Ax+e’)$ by subtracting $Ax$ from the third entry and seeing if the entries look uniform or Gaussian.

Distinguishing $(x,1,u)$ from $(x,1,A(x+s)+(e+e’))$ is a standard LWE problem (noting that the variance of $e+e’$ is the sum of the variances of $e$ and $e’$.

Thus samples with $b=0$ are trivial and samples with $b=1$ Are presumably not. Taking polynomially many samples is virtually certain to give at least one with $b=0$ and so allow us to distinguish trivially.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Just to sanity check, if there were polynomially many samples from either \begin{equation} (x, b_1, b_2, \ldots, b_k, ~Ax + b_1\cdot(As_1 + e_1) + b_2\cdot(As_2 + e_2) + \cdots + b_k\cdot(As_k + e_k) + e') ~~\text{or}~~\left(x, b_1, b_2, \ldots, b_k, u \right), \end{equation} for $b_i \in \{0, 1\}$, for a polynomially large $k$ and for secret vectors $s_1, \ldots, s_k$, then these will be indistinguishable, is that right? $\endgroup$
    – Morbius
    Commented Apr 15, 2022 at 0:39
  • $\begingroup$ The argument is just that when every $b_i$ is $0$, they are easily distinguishable, but such a case is exponentially unlikely. For every other case, for any choice of $k$, we can reduce it to LWE. $\endgroup$
    – Morbius
    Commented Apr 15, 2022 at 0:42
  • $\begingroup$ No, the argument is that if at least $b_i$ is 0, the set is easily distinguishable $\endgroup$
    – Daniel S
    Commented Apr 15, 2022 at 5:52
  • $\begingroup$ How can that be true? Let's say only $b_1 = 0$. Then, we are essentially distinguishing between $A(x + s_2 + s_3 + \cdots + s_k) + (e_1 + e_2 + \cdots + e_k) + e'$ and $u$. Isn't that just a variant of LWE? So, do we not need every $b_i$ to be $0$ for the samples to be distinguishable and not just at least one $b_i$ to be $0$? $\endgroup$
    – Morbius
    Commented Apr 16, 2022 at 5:36
  • $\begingroup$ *We are distinguishing between $A(x + s_2 + \cdots + s_k) + (e_2 + \cdots + e_k + e')$ and $u$.... $\endgroup$
    – Morbius
    Commented Apr 16, 2022 at 5:46

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.