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
Abstract

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint.
Keywords
Fully Homomorphic EncryptionBGVnon-power-of-twoparameter estimation
Contact author(s)
andreadigiusto7 @ gmail com
chiara marcolla @ tii ae
History
2023-11-01: revised
2023-05-29: received
See all versions
Short URL
https://ia.cr/2023/783
License
Creative Commons Attribution-NonCommercial-ShareAlike
CC BY-NC-SA

BibTeX

@misc{cryptoeprint:2023/783,
      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{https://eprint.iacr.org/2023/783}},
      url = {https://eprint.iacr.org/2023/783}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.