Paper 2017/748

Efficient reductions in cyclotomic rings - Application to R-LWE based FHE schemes

Jean-Claude Bajard, Julien Eynard, Anwar Hasan, Paulo Martins, Leonel Sousa, and Vincent Zucca


With Fully Homomorphic Encryption (FHE), it is possible to process encrypted data without having an access to the private-key. This has a wide range of applications, most notably the offloading of sensitive data processing. Most research on FHE has focused on the improvement of its efficiency, namely by introducing schemes based on the Ring-Learning With Errors (R-LWE) problem, and techniques such as batching, which allows for the encryption of multiple messages in the same ciphertext. Much of the related research has focused on RLWE relying on power-of-two cyclotomic polynomials. While it is possible to achieve efficient arithmetic with such polynomials, one cannot exploit batching. Herein, the efficiency of ring arithmetic underpinned by non-power-of-two cyclomotic polynomials is analysed and improved. Two methods for polynomial reduction are proposed, one based on the Barrett reduction and the other on a Montgomery representation. Speed-ups up to 2.66 are obtained for the reduction operation using an i7-5960X processor when compared with a straightforward implementation of the Barrett reduction. Moreover, the proposed methods are exploited to enhance homomorphic multiplication of FV and BGV encryption schemes, producing experimental speed-ups up to 1.37.

Available format(s)
Publication info
Published elsewhere. Selected Areas of Cryptoraphy 2017
Polynomial ReductionNumber Theoretic TransformResidue Number SystemsRing-Learning With ErrorsHomomorphic Encryption
Contact author(s)
vincent zucca @ lip6 fr
2017-08-07: received
Short URL
Creative Commons Attribution


      author = {Jean-Claude Bajard and Julien Eynard and Anwar Hasan and Paulo Martins and Leonel Sousa and Vincent Zucca},
      title = {Efficient reductions in cyclotomic rings - Application to R-LWE based FHE schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2017/748},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.