Paper 2023/104 Original: eprint.iacr.org/2023/104 ↗
Optimizations and Trade-offs for HElib
Abstract
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.
Metadata
- Available format(s)
PDF- Category
- Public-key cryptography
- Publication info
- Preprint.
- History
- 2023-05-02: last updated
- 2023-01-27: published
- Short URL
- https://ia.cr/2023/104
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2023/104,
author = {Anamaria Costache and Lea Nürnberger and Rachel Player},
title = {Optimizations and Trade-offs for HElib},
howpublished = {Cryptology {ePrint} Archive, Paper 2023/104},
year = {2023},
url = {https://eprint.iacr.org/2023/104}
}