Paper 2020/1355

Modular Lagrange Interpolation of the Mod Function for Bootstrapping of Approximate HE

Charanjit S. Jutla and Nathan Manohar

Abstract

We introduce a novel variant of Lagrange interpolation called modular Lagrange interpolation that allows us to obtain and prove error bounds for explicit low-degree polynomial approximations of a function on a union of equally-spaced small intervals even if the function overall is not continuous. We apply our technique to the mod function and obtain explicit low-degree polynomial approximations with small error. In particular, for every $k$ and $N >>k$, we construct low-degree polynomials that approximate $f(x) = x \mod N$, for $|f(x)| \leq 1$ and $|x| \leq kN$, to within O($1/N$) additive approximation. For $k= O(\log N)$, the result is generalized to give O($d$)-degree polynomial approximations to within O($N^{-d}$) error for any $d \geq 1$. Literature in approximation theory allows for arbitrary precision polynomial approximation of only smooth functions, whereas the mod function is only piecewise linear. These polynomials can be used in bootstrapping for approximate homomorphic encryption, which requires computing the mod function near multiples of the modulus. Our work bypasses the fundamental error of approximation in prior works caused by first approximating the mod function by a scaled sine function. We implement the bootstrapping of $\mathsf{HEAAN}$ using our polynomials and profile various parameter settings. For example, we demonstrate bootstrapping that can achieve 67 bit message precision, larger than the precision of a $\mathsf{double}$ variable, whereas the most advanced prior work was only capable of up to 40 bit message precision.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
homomorphic encryptionpolynomial interpolationmachine learningChebyshev polynomials
Contact author(s)
csjutla @ us ibm com
nmanohar @ cs ucla edu
History
2021-05-27: last of 2 revisions
2020-10-29: received
See all versions
Short URL
https://ia.cr/2020/1355
License
Creative Commons Attribution
CC BY

BibTeX

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