Paper 2020/1355

Modular Lagrange Interpolation of the Mod Function for Bootstrapping for 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. For typical settings of $N$, these polynomials have lower error than the fundamental error introduced by using the scaled sine function at degrees computable in multiplicative depth seven or eight.