**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.

**Category / Keywords: **public-key cryptography / homomorphic encryption, polynomial interpolation, machine learning, Chebyshev polynomials

**Date: **received 27 Oct 2020, last revised 29 Oct 2020

**Contact author: **csjutla at us ibm com

**Available format(s): **PDF | BibTeX Citation

**Version: **20201029:150905 (All versions of this report)

**Short URL: **ia.cr/2020/1355

[ Cryptology ePrint archive ]