Welcome to the resource topic for 2023/783
Title:
Breaking the power-of-two barrier: noise estimation for BGV in NTT-friendly rings
Authors: Andrea Di Giusto, Chiara Marcolla
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 can sometimes also cause a jump of 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 3^t, i.e., cyclotomic polynomials with degree n=2^s 3^{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.
ePrint: https://eprint.iacr.org/2023/783
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .