Paper 2021/572

Sine Series Approximation of the Mod Function for Bootstrapping of Approximate HE

Charanjit Singh Jutla and Nathan Manohar

Abstract

While it is well known that the sawtooth function has a point-wise convergent Fourier series, the rate of convergence is not the best possible for the application of approximating the mod function in small intervals around multiples of the modulus. We show a different sine series, such that the sine series of order n has error O(epsilon^(2n+1)) for approximating the mod function in epsilon-sized intervals around multiples of the modulus. Moreover, the resulting polynomial, after Taylor series approximation of the sine series, has small coefficients, and the whole polynomial can be computed at a precision that is only slightly larger than -(2n+1)log epsilon, the precision of approximation being sought. This polynomial can then be used to approximate the mod function to almost arbitrary precision, and hence allows practical CKKS-HE bootstrapping with arbitrary precision. We validate our approach with an implementation and obtain 100 bit precision bootstrapping as well as improvements over earlier works at lower precision.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. Minor revision.
Keywords
FHEFourier seriesSine seriesalternating seriesmod functionbootstrapping
Contact author(s)
nmanohar @ cs ucla edu
csjutla @ us ibm com
History
2021-10-27: last of 5 revisions
2021-05-03: received
See all versions
Short URL
https://ia.cr/2021/572
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/572,
      author = {Charanjit Singh Jutla and Nathan Manohar},
      title = {Sine Series Approximation of the Mod Function for Bootstrapping of Approximate HE},
      howpublished = {Cryptology ePrint Archive, Paper 2021/572},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/572}},
      url = {https://eprint.iacr.org/2021/572}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.