Cryptology ePrint Archive: Report 2019/1266

Note on the noise growth of the RNS variants of the BFV scheme

Jean Claude Bajard and Julien Eynard and Paulo Martins and Leonel Sousa and Vincent Zucca

Abstract: In a recent work, Al Badawi et al. have noticed a different behaviour of the noise growth in practice between the two RNS variants of BFV from Bajard et al. and Halevi et al. Their experiments, based on the PALISADE and SEAL libraries, have shown that the multiplicative depth reached, in practice, by the first one was considerably smaller than the second one while theoretically equivalent in the worst-case. Their interpretation of this phenomenon was that the approximations used by Bajard et al. made the expansion factor behave differently than what the Central Limit Theorem would predict. We have realized that this difference actually comes from the implementation of the SmMRq procedure of Bajard et al. in SEAL and PALISADE which is slightly different than what Bajard et al. had proposed. In this note we show that by fixing this small difference, the multiplicative depth of both variants is actually the same in practice.

Category / Keywords: public-key cryptography / Lattice-based Cryptography, Homomorphic Encryption, BFV, Residue Number Systems, Software Implementation

Date: received 31 Oct 2019, last revised 5 Nov 2019

Contact author: vincent zucca at kuleuven be

Available format(s): PDF | BibTeX Citation

Version: 20191105:085145 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]