Paper 2023/104

Optimizations and Trade-offs for HElib

Anamaria Costache, Norwegian University of Science and Technology (NTNU)
Lea Nürnberger, Norwegian University of Science and Technology (NTNU)
Rachel Player, Royal Holloway, University of London
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
Published elsewhere. CT-RSA 2023
Keywords
fully homomorphic encryptionlattice-based cryptography
Contact author(s)
anamaria costache @ ntnu no
lea nurnberger @ ntnu no
Rachel Player @ rhul ac uk
History
2023-05-02: revised
2023-01-27: received
See all versions
Short URL
https://ia.cr/2023/104
License
Creative Commons Attribution
CC BY

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