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

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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
Lattice-based CryptographyHomomorphic EncryptionBFVResidue Number SystemsSoftware Implementation
Contact author(s)
vincent zucca @ kuleuven be
History
2019-11-19: last of 3 revisions
2019-11-05: received
See all versions
Short URL
https://ia.cr/2019/1266
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/1266,
      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{https://eprint.iacr.org/2019/1266}},
      url = {https://eprint.iacr.org/2019/1266}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.