2
$\begingroup$

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

$\endgroup$
8
  • $\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, 2018 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, 2018 at 3:15
  • $\begingroup$ What does $\chi^m$ mean? $\endgroup$
    – kodlu
    Jul 31, 2018 at 3:24
  • $\begingroup$ The error vector is drawn from a distribution (Gaussian) $\endgroup$
    – chelsea
    Jul 31, 2018 at 3:28
  • 1
    $\begingroup$ if R is uniformly random , then so is A+R. $\endgroup$
    – user27950
    Jul 31, 2018 at 5:32

1 Answer 1

3
$\begingroup$

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.

$\endgroup$
4
  • $\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$ Aug 1, 2018 at 8:12
  • $\begingroup$ $(A',b')$ is the LWE sample, $R$ is built from public values $A'$ and $A$. $\endgroup$ Aug 1, 2018 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$ Aug 1, 2018 at 8:43
  • $\begingroup$ I edited the answer to make it more formal $\endgroup$ Aug 1, 2018 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.