You are looking at a specific version 20200715:115109 of this paper. See the latest version.

Paper 2019/493

Evaluating the effectiveness of heuristic worst-case noise analysis in FHE

Anamaria Costache and Kim Laine and Rachel Player

Abstract

The purpose of this paper is to test the accuracy of worst-case heuristic bounds on the noise growth in ring-based homomorphic encryption schemes. We use the methodology of Iliashenko (PhD thesis, 2019) to provide a new heuristic noise analysis for the BGV scheme. We demonstrate that for both the BGV and FV schemes, this approach gives tighter bounds than previous heuristic approaches, by as much as 10 bits of noise budget. Then, we provide experimental data on the noise growth of HElib and SEAL ciphertexts, in order to evaluate how well the heuristic bounds model the noise growth in practice. We find that, in spite of our improvements, there is still a gap between the heuristic estimate of the noise and the observed noise in practice. We extensively justify that a heuristic worst-case approach inherently leads to this gap, and hence leads to selecting significantly larger parameters than needed. As an additional contribution, we update the comparison between the two schemes presented by Costache and Smart (CT-RSA, 2016). Our new analysis shows that the practical crossover point at which BGV begins to outperform FV occurs for very large plaintext moduli, well beyond the crossover point reported by Costache and Smart.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Published elsewhere. To appear at ESORICS 2020
Keywords
Fully Homomorphic EncryptionLattice CryptographyPublic-Key Encryption
Contact author(s)
Anamaria Costache @ rhul ac uk
History
2020-07-15: last of 2 revisions
2019-05-20: received
See all versions
Short URL
https://ia.cr/2019/493
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.