A query on Learning with errors(LWE) problem

Question

In generating an LWE sample, we do

$s\xleftarrow{$}\mathbb{Z}_q^{n}, A \xleftarrow{$}\mathbb{Z}_q^{n \times m}~$and $e\xleftarrow{$}\mathbb{{\chi}^{m}}$

Then we compute $b^T$ = $s^TA$ + $e^T$ and the sample $(A,b)$ $\approx$ truly random sample.

Now suppose we have a fixed matrix (not random and public) $A \in\mathbb{Z}_q^{n \times m}$. We choose $R\xleftarrow{$}\mathbb{Z}_q^{n \times m}$ and compute $A' = A + R$ and the generate the LWE sample as $(A',b')$.

Will the LWE assumption still hold? If it doesn't hold, then is there a way to mask matrix $A$?

Answer 1

It is easy to reduce this problem to LWE, since adding any element to a uniformly random value gives a uniformly random distribution.

For example, here, $(A',b')$ is distributed the same as if $A'$ was drawn uniformly randomly, and $R$ set as $A'-A$. You're now in the setting of the LWE assumption and can replace $b'$ by a uniformly random value without anybody (PPT) noticing it. With more details:

$$R\gets\mathbb{Z}_q^{n\times m}, A' := A + R, b'^t := s^t A'+ e^t, e\gets \chi^m,$$

is distributed identically to:

$$A'\gets\mathbb{Z}_q^{n\times m}, R := A' - A, b'^t := s^t A' + e^t, e\gets \chi^m,$$

which is computationally indistinguishable from:

$$A'\gets\mathbb{Z}_q^{n\times m}, R := A' - A, b' \gets \mathbb{Z}_q^{m}.$$

You can then switch back to normal generation of $A'$: the previous distribution is identical to:

$$R\gets\mathbb{Z}_q^{n\times m}, A' := A + R, b' \gets \mathbb{Z}_q^{m}.$$

Edit: added more details to clarify the answer.