1
$\begingroup$

I am wondering why the modulus $q$ in the LWE problem has to be polynomial in $n$.

Another question is whether one can take it to be an arbitrary integer instead of a prime number.

$\endgroup$
4
  • $\begingroup$ Are you asking why $q\in O(poly(n))$, or why $q\in \Omega(poly(n))$? $\endgroup$
    – Ievgeni
    Oct 18, 2021 at 11:53
  • $\begingroup$ @Ievgeni It is $O(\text{poly}(n)$ $\endgroup$
    – C.S.
    Oct 18, 2021 at 12:40
  • $\begingroup$ Could you precise where did you see q should be in $O(poly(n))$? $\endgroup$
    – Ievgeni
    Oct 18, 2021 at 12:43
  • $\begingroup$ @Ievgeni it is here cims.nyu.edu/~regev/papers/lwesurvey.pdf The section "Parameters" at the end of page 2. Thanks a lot! $\endgroup$
    – C.S.
    Oct 18, 2021 at 12:57

1 Answer 1

0
$\begingroup$

I think the answer is in the document you've found the recommendation : "Choosing an exponential modulus $q$ has the disadvantage of significantly increasing the size of the input."

$\endgroup$
2
  • $\begingroup$ Yes but what is the input here? Input of what? $\endgroup$
    – C.S.
    Oct 18, 2021 at 13:03
  • $\begingroup$ $(\vec a, 〈\vec a, s〉+ e)$ $\endgroup$
    – Ievgeni
    Oct 18, 2021 at 13:06

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.