Cryptology ePrint Archive: Report 2019/493

Homomorphic noise growth in practice: comparing BGV and FV

Anamaria Costache and Kim Laine and Rachel Player

Abstract: The purpose of this paper is to provide a comprehensive analysis and side-by-side comparison of the noise growth behaviour in the BGV and FV somewhat homomorphic encryption schemes, both heuristically and in their implementations in the libraries HElib and SEAL, respectively. We run extensive experiments in HElib and SEAL to com- pare the heuristic noise growth to the noise growth in practice. From the experiments, we observe that for both schemes, the heuristic bounds are not tight. We attempt to improve the tightness of the bounds in a num- ber of ways, including the definition of new notions of noise, such as the invariant noise for BGV and the scaled inherent noise for FV. This does not significantly tighten the bounds, thus we conclude that the current heuristic bounds are the best possible in terms of a theoretical analysis. As an additional contribution, we update the comparison between the two schemes presented by Costache and Smart [22], and find that BGV has a slight advantage over FV. Thus, the conclusions of [22] still hold, although the differences between BGV and FV are less dramatic.

Category / Keywords: public-key cryptography / Fully Homomorphic Encryption, Lattice Cryptography, Public-Key Encryption

Date: received 13 May 2019

Contact author: Anamaria costache at intel com

Available format(s): PDF | BibTeX Citation

Version: 20190520:112814 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]