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.
4
-
$\begingroup$ Are you asking why $q\in O(poly(n))$, or why $q\in \Omega(poly(n))$? $\endgroup$– IevgeniOct 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$– IevgeniOct 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
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
2
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."
-
$\begingroup$ Yes but what is the input here? Input of what? $\endgroup$– C.S.Oct 18, 2021 at 13:03
-