IACR News item: 27 January 2023
Anamaria Costache, Lea Nürnberger, Rachel Player
ePrint Report
In this work, we investigate the BGV scheme as implemented
in HElib. We begin by performing an implementation-specific noise analysis of BGV. This allows us to derive much tighter bounds than what
was previously done. To confirm this, we compare our bounds against the state of the art. We find that, while our bounds are at most $1.8$ bits off the experimentally observed values, they are as much as $29$ bits tighter than previous work. Finally, to illustrate the importance of our results, we propose new and optimised parameters for HElib. In HElib, the special modulus is chosen to be $k$ times larger than the current ciphertext modulus $Q_i$. For a ratio of subsequent ciphertext moduli $\log\left( \frac{Q_i}{Qi−1}\right) = 54$ (a very common choice in HElib), we can optimise $k$ by up to $26$ bits. This means that we can either enable more multiplications without having to switch to larger parameters, or reduce the size of the evaluation keys, thus reducing on communication costs in relevant applications. We argue that our results are near-optimal.
Additional news items may be found on the IACR news page.