Approximation Methods Part I: A General Overview

The arithmetic of modern fully homomorphic encryption (FHE) schemes is basically limited to addition, subtraction, and multiplication, so that most computations are actually evaluations of some finite (possibly multivariate) polynomial over the input ciphertexts. Thus, FHE computations that involve functions that cannot be expressed with a finite polynomial (e.g., division, square roots, or trigonometric functions) must be approximated with some finite polynomial, and finding the “best” estimating polynomial and the “best” way to evaluate it is part of the art of developing FHE applications. Section 4.8 described and compared different methods for evaluating polynomials under FHE. This section describes some general aspects that should be considered when looking for the best polynomial to approximate a given targeted function under FHE and then proceeds to describe some specific methods used for finding such polynomial approximations for general functions. The next chapter (Chap. 6 ) will then show how to use these and other more targeted techniques to approximate specific useful functions, such as comparisons, reciprocals, trigonometric functions, and activation functions.