Paper 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.
Metadata
- Available format(s)
- Category
- Public-key cryptography
- Publication info
- Preprint. MINOR revision.
- Keywords
- Fully Homomorphic EncryptionLattice CryptographyPublic-Key Encryption
- Contact author(s)
- Anamaria costache @ intel com
- History
- 2020-07-15: last of 2 revisions
- 2019-05-20: received
- See all versions
- Short URL
- https://ia.cr/2019/493
- License
-
CC BY