# R-LWE instantiation with non-power of 2 polynomial

In almost all RLWE papers, the polynomials are chosen from a ring $\mathbb{Z}[x]/f(x)$ where $f(x)$ is a polynomial of the form $f(x)=x^{2^n}+1$. That leaves us the choice of polynomials like $x^{256}+1$, $x^{512}+1$ or $x^{1024}+1$ etc. Apart from irreducibility, I understand that using this polynomial has few other advantages like fast polynomial multiplication. One disadvantage of this is that it makes the sizes of keys or ciphertexts or signatures bigger. Just for example in the NewHope key-exchange scheme, their proposed parameter uses a polynomial of degree $1024$ which provides much more than $128$ bit security, whereas the less secure version (JARJAR) uses a polynomial of degree $512$ but provides security less than $128$ bits. Evidently, the former version sends much more data over the wire than the latter one. But, what if I want to use a polynomial of degree that is between the above two, for example, $768$, it will provide sufficient security and will use a lesser amount of data.

Now my questions are

1. Can I use cyclotomic polynomial $\phi_{3*768}= x^{768} - x^{384} + 1$ as a modulus?

2. If yes, does the error distribution change? By what degree? (I understand there are some issues described in this paper (How (Not) to Instantiate Ring-LWE) but it is little difficult for me)

• From what I know so far, It's indeed been used. The error distribution change for signatures had been described in the paper I've linked, and as for KEMs, I suppose non-power-of-two polynomials may cause error propagation to be greater, which makes reconciliation more difficult. Jul 20, 2017 at 11:49
• @DannyNiu Thanks, I did not know that. I will look into it.
– Rick
Jul 20, 2017 at 11:58
• @DannyNiu I did not see a discussion on error distribution in your referenced paper. Can you please mention the section?
– Rick
Jul 20, 2017 at 12:30
• I thought change in standard deviation might count as error distribution change. The paper mentioned how to derive parameters for the BLISS scheme. Discrete Gaussian is very much preferred in signature schemes so I don't think we need to change the "shape". Jul 20, 2017 at 12:35
• @Rick It's worth stating that if your goal is post-quantum security, you may want to consider schemes such as NTRU Prime. I say this because if your use of a cyclotomic polynomial introduces any periodicity, it may not be pq-secure. Also worth mentioning, Lyubashevsky stated at PQCrypto '17 that they are moving away from Gaussians due to weaknesses introduced by this component. Jul 22, 2017 at 16:41