Paper 2019/493

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

Anamaria Costache, Kim Laine, and Rachel Player


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.

Available format(s)
Public-key cryptography
Publication info
Published elsewhere. To appear at ESORICS 2020
Fully Homomorphic EncryptionLattice CryptographyPublic-Key Encryption
Contact author(s)
Anamaria Costache @ rhul ac uk
2020-07-15: last of 2 revisions
2019-05-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anamaria Costache and Kim Laine and Rachel Player},
      title = {Evaluating the effectiveness of heuristic worst-case noise analysis in FHE},
      howpublished = {Cryptology ePrint Archive, Paper 2019/493},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.