Welcome to the resource topic for 2020/1355
Title:
Modular Lagrange Interpolation of the Mod Function for Bootstrapping of Approximate HE
Authors: Charanjit S. Jutla, 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.
ePrint: https://eprint.iacr.org/2020/1355
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .