Paper 2019/1266

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

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


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.

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
Lattice-based CryptographyHomomorphic EncryptionBFVResidue Number SystemsSoftware Implementation
Contact author(s)
vincent zucca @ kuleuven be
2019-11-19: last of 3 revisions
2019-11-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Jean Claude Bajard and Julien Eynard and Paulo Martins and Leonel Sousa and Vincent Zucca},
      title = {Note on the noise growth of the RNS variants of the BFV scheme},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1266},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.