# Computational indistinguishability of two LWE type samples

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

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,

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

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

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.
• Just to sanity check, if there were polynomially many samples from either $$(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),$$ 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? Commented Apr 15, 2022 at 0:39
• 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. Commented Apr 15, 2022 at 0:42
• No, the argument is that if at least $b_i$ is 0, the set is easily distinguishable Commented Apr 15, 2022 at 5:52
• 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$? Commented Apr 16, 2022 at 5:36
• *We are distinguishing between $A(x + s_2 + \cdots + s_k) + (e_2 + \cdots + e_k + e')$ and $u$.... Commented Apr 16, 2022 at 5:46