Paper 2023/783

Breaking the power-of-two barrier: noise estimation for BGV in NTT-friendly rings

Andrea Di Giusto
Chiara Marcolla, Technology Innovation Institute

The Brakerski-Gentry-Vaikuntanathan (BGV) scheme is a Fully Homomorphic Encryption (FHE) cryptosystem based on the Ring Learning With Error (RLWE) problem. Ciphertexts in this scheme contain an error term that grows with operations and causes decryption failure when it surpasses a certain threshold. For this reason, the parameters of BGV need to be estimated carefully, with a trade-off between security and error margin. The ciphertext space of BGV is the ring $\mathcal R_q=\mathbb Z_q[x]/(\Phi_m(x))$, where usually the degree $n$ of the cyclotomic polynomial $\Phi_m(x)$ is chosen as a power of two for efficiency reasons. However, the jump between two consecutive powers-of-two polynomials also causes a jump in the security, resulting in parameters that are much bigger than what is needed. In this work, we explore the non-power-of-two instantiations of BGV. Although our theoretical research encompasses results applicable to any cyclotomic ring, our main investigation is focused on the case of ${m=2^s\cdot3^t}$, i.e., cyclotomic polynomials with degree ${n=\phi(m)=2^s\cdot3^{t-1}}$. We provide a thorough analysis of the noise growth in this new setting using the canonical norm and compare our results with the power-of-two case considering practical aspects like NTT algorithms. We find that in many instances, the parameter estimation process yields better results for the non-power-of-two setting.

Available format(s)
Public-key cryptography
Publication info
Fully Homomorphic EncryptionBGVnon-power-of-twoparameter estimation
Contact author(s)
andreadigiusto7 @ gmail com
chiara marcolla @ tii ae
2023-11-01: revised
2023-05-29: received
See all versions
Short URL
Creative Commons Attribution-NonCommercial-ShareAlike


      author = {Andrea Di Giusto and Chiara Marcolla},
      title = {Breaking the power-of-two barrier: noise estimation for {BGV} in {NTT}-friendly rings},
      howpublished = {Cryptology ePrint Archive, Paper 2023/783},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.