Cryptology ePrint Archive: Report 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.

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

Original Publication (in the same form): To appear at ESORICS 2020

Date: received 13 May 2019, last revised 15 Jul 2020

Contact author: Anamaria Costache at rhul ac uk

Available format(s): PDF | BibTeX Citation

Version: 20200715:115109 (All versions of this report)

Short URL: ia.cr/2019/493


[ Cryptology ePrint archive ]