[Resource Topic] 2023/104: Optimizations and Trade-offs for HElib

Welcome to the resource topic for 2023/104

Optimizations and Trade-offs for HElib

Authors: Anamaria Costache, Lea Nürnberger, Rachel Player


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.

ePrint: https://eprint.iacr.org/2023/104

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 .