3
$\begingroup$

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)

Thank you for your help.

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – DannyNiu Jul 20 '17 at 11:49
  • $\begingroup$ @DannyNiu Thanks, I did not know that. I will look into it. $\endgroup$ – Rick Jul 20 '17 at 11:58
  • $\begingroup$ @DannyNiu I did not see a discussion on error distribution in your referenced paper. Can you please mention the section? $\endgroup$ – Rick Jul 20 '17 at 12:30
  • $\begingroup$ 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". $\endgroup$ – DannyNiu Jul 20 '17 at 12:35
  • 1
    $\begingroup$ @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. $\endgroup$ – nonce Jul 22 '17 at 16:41
1
$\begingroup$

On the IACR eprint archive there is a paper entitled "Even More Practical Key Exchanges for the Internet using Lattice Cryptography" by Singh and Chopra that discusses using other cyclotomic fields which provide the same security guarantees as the power of 2 cyclotomic case.

One reason why these other cyclotomics are not as popular is that the speed of the Nunber Theoretic Transform in these other cyclotomics is not as computationally efficient. Nevertheless as you point out there is a legitimate tradeoff between parameter sizes and computation.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.