Regev requires $q$ to be prime on lemma 4.2 of his paper for LWE.

Why does he require that and how this effect the proof of lemma 4.2?


1 Answer 1


He needs to add something uniformly random to the second coordinate, to get a distribution that is uniformly random. (The idea is that if he guesses the correct key, his rerandomization turns real instances into real instances. If he guesses the wrong key, his rerandomization should turn real instances into random instances.)

If $p$ is a prime, then multiplication by any non-zero value is a bijection, so a uniformly distributed $l$ maps to a uniformly distributed product $l(k-s_1)$.

If $p$ is composite, then multiplication by a value that isn't relatively prime to $p$ would not be a bijection, so a uniformly distributed $l$ might not map to a uniformly distributed product $l(k-s_1)$.

  • $\begingroup$ Thank you for your answer, can you recommend to me a paper with a mathematical proof that these results relied on? It would be very helpfull. $\endgroup$
    – Mike Anast
    Jun 14, 2018 at 18:24
  • $\begingroup$ @MikeAnast I would not look for papers, but for an introduction to number theory and perhaps also an introduction to statistics. $\endgroup$
    – K.G.
    Jun 22, 2018 at 2:05
  • $\begingroup$ I think i found the answer on lemma 4.2 in [eprint.iacr.org/2011/521.pdf]. I would appreciate your opinion to this. $\endgroup$
    – Mike Anast
    Jun 23, 2018 at 14:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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