Score:1

Why $q$ in LWE must be polynomial in $n$

in flag

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.

Ievgeni avatar
cn flag
Are you asking why $q\in O(poly(n))$, or why $q\in \Omega(poly(n))$?
C.S. avatar
in flag
@Ievgeni It is $O(\text{poly}(n)$
Ievgeni avatar
cn flag
Could you precise where did you see q should be in $O(poly(n))$?
C.S. avatar
in flag
@Ievgeni it is here https://cims.nyu.edu/~regev/papers/lwesurvey.pdf The section "Parameters" at the end of page 2. Thanks a lot!
Score:0
cn flag

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."

C.S. avatar
in flag
Yes but what is the input here? Input of what?
Ievgeni avatar
cn flag
$(\vec a, 〈\vec a, s〉+ e)$
mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.