1
$\begingroup$

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?

Thanks!

$\endgroup$

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.