The usual RLWE cryptographic constructions that I have read uses the parameters $n$ to be a power of two and $q$ a prime such that $q\equiv 1 \mod (2n)$. Do I understand it correctly that the reason we choose $q$ to be that way is that the polynomial $X^n+1$ will split into linear factors which allows a CRT representation for the elements in $R_q=\mathbb{Z}_q[X]/(X^n+1)$?

On the other hand, I saw a paper of Lyubashevksy about Efficient Zero-Knowledge Proofs based on RLWE and they choose $q$ to be a prime such that $q\equiv 3\mod 8$ hence $X^n+1$ only factors into two irreducible factors. My question is, with $q\equiv 3\mod 8$, do we still have a CRT representation on $R_q$?

In general, how do we choose $q$ and $n$ for constructing RLWE cryptographic protocol for it to be secure and efficient enough to implement?



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.