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

  • $\begingroup$ 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? $\endgroup$ – Ella Rose Jul 31 '18 at 1:35
  • 1
    $\begingroup$ A deterministic algorithm is run to generate the entries of $A$ and then it's made public. $\endgroup$ – chelsea Jul 31 '18 at 3:15
  • $\begingroup$ What does $\chi^m$ mean? $\endgroup$ – kodlu Jul 31 '18 at 3:24
  • $\begingroup$ The error vector is drawn from a distribution (Gaussian) $\endgroup$ – chelsea Jul 31 '18 at 3:28
  • 1
    $\begingroup$ if R is uniformly random , then so is A+R. $\endgroup$ – user27950 Jul 31 '18 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}.$$

Edit: added more details to clarify the answer.

| improve this answer | |
  • $\begingroup$ 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$... $\endgroup$ – Hilder Vitor Lima Pereira Aug 1 '18 at 8:12
  • $\begingroup$ $(A',b')$ is the LWE sample, $R$ is built from public values $A'$ and $A$. $\endgroup$ – Florian Bourse Aug 1 '18 at 8:23
  • $\begingroup$ 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$"? $\endgroup$ – Hilder Vitor Lima Pereira Aug 1 '18 at 8:43
  • $\begingroup$ I edited the answer to make it more formal $\endgroup$ – Florian Bourse Aug 1 '18 at 8:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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