# A query on Learning with errors(LWE) problem

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$?

• When you say Now suppose we have a fixed matrix (not random and public) , what are the entries in the matrix if it is not random? Or do you mean a random but publicly known matrix? Jul 31, 2018 at 1:35
• A deterministic algorithm is run to generate the entries of $A$ and then it's made public. Jul 31, 2018 at 3:15
• What does $\chi^m$ mean? Jul 31, 2018 at 3:24
• The error vector is drawn from a distribution (Gaussian) Jul 31, 2018 at 3:28
• if R is uniformly random , then so is A+R.
– user27950
Jul 31, 2018 at 5:32

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

• I am not sure that $(R, b')$ is a valid LWE sample because here $b'$ doesn't have the format $s^T R + e$, since there is that additional term $s^T A$... Aug 1, 2018 at 8:12
• $(A',b')$ is the LWE sample, $R$ is built from public values $A'$ and $A$. Aug 1, 2018 at 8:23
• Yes, $(A', b')$ is a LWE sample. But what I understood from "You're now in the setting of the LWE assumption" is that $(R, b')$ is a LWE sample. So I think I didn't get it. Thus, please, could you explain what you mean by that and by "$R$ set as $A' - A$"? Aug 1, 2018 at 8:43
• I edited the answer to make it more formal Aug 1, 2018 at 8:56