Polynomial Approximation

Homomorphic encryption (HE) schemes like CKKS and BFV are algebraically restricted to addition and multiplication operations on ciphertexts. Non-linear functions—such as ReLU, sigmoid, tanh, and max pooling—cannot be evaluated directly. Polynomial approximation replaces these functions with polynomials that can be computed using only the allowed operations.

• Core Insight: Any continuous function on a closed interval can be uniformly approximated by a polynomial (Weierstrass approximation theorem).
• Practical Impact: This transforms an incompatible neural network into a circuit evaluable under encryption.

Several mathematical techniques are employed to find the optimal polynomial representation, each with distinct trade-offs in accuracy and computational depth.

• Minimax Approximation: Finds the polynomial that minimizes the maximum absolute error over the target interval. The Remez algorithm is the standard tool, producing the optimal polynomial for a given degree.
• Least Squares Fitting: Minimizes the average squared error, often using Chebyshev nodes to avoid Runge's phenomenon at interval boundaries.
• Taylor Series: A simple local approximation around a single point, but error grows rapidly away from the expansion point, making it unsuitable for wide intervals.
• Interpolation: Forces the polynomial to match the target function exactly at specific points, but can oscillate wildly between them if not carefully designed.

The choice of polynomial degree directly impacts both the approximation error and the computational cost under encryption.

• Higher Degree = Better Accuracy: A degree-7 polynomial can approximate ReLU with near-perfect fidelity on a bounded interval, while a degree-3 polynomial introduces noticeable smoothing.
• Higher Degree = Greater Depth: Each polynomial evaluation consumes the noise budget and requires a specific multiplicative depth. A degree-7 polynomial requires a circuit depth of 3 (using Horner's method or Estrin's scheme), while degree-3 requires depth 2.
• Bootstrapping Cost: If the required depth exceeds the scheme's native capacity, a computationally expensive bootstrapping operation is needed to refresh the ciphertext, often dominating inference latency.

Polynomial approximations are only accurate within a predefined bounded interval. Inputs outside this range cause catastrophic error divergence.

• Input Normalization: Neural network activations must be statistically bounded. Techniques like batch normalization and fixed scaling ensure inputs stay within the approximation's valid domain.
• Piecewise Polynomials: For functions with complex behavior, the domain is split into sub-intervals, each with its own low-degree polynomial. Under HE, selecting the correct sub-interval requires a multiplexer implemented via encrypted comparisons.
• Composition: Functions like softmax are decomposed into a sequence of approximable primitives: exponential approximation, summation, and reciprocal approximation.

Common neural network activation functions have well-studied polynomial substitutes optimized for HE evaluation.

• ReLU → Square or Low-Degree Polynomial: The standard ReLU, max(0, x), is replaced by x² or a degree-4 minimax polynomial that closely tracks the ReLU shape on [-1, 1].
• Sigmoid / Tanh → Low-Degree Minimax: These smooth functions are well-approximated by degree-3 or degree-5 polynomials on a bounded interval like [-8, 8].
• Max Pooling → Scaled Mean or Polynomial Softmax: The non-differentiable max operation is replaced by a smooth approximation like the LogSumExp function, which itself is built from exponentials and logarithms, each requiring polynomial approximation.
• Division → Reciprocal Approximation: For operations like batch normalization, division is implemented by approximating 1/x with a polynomial and multiplying.

The inherent approximation error must be evaluated against the application's tolerance for numerical imprecision.

• CKKS and Approximate Arithmetic: The CKKS scheme is designed for approximate fixed-point arithmetic, making it the natural pairing for polynomial approximation. It treats least-significant-bit errors as noise, aligning with the approximation error.
• Inference vs. Training: Encrypted inference is highly practical with polynomial approximations, as a pre-trained model's weights are fixed and the approximation error can be validated offline. Encrypted training is significantly harder because gradients must also be approximated, compounding errors.
• Accuracy Validation: The final encrypted model's accuracy must be benchmarked against the original plaintext model on a held-out test set to ensure the approximation error does not degrade predictive performance below acceptable thresholds.

Every homomorphic multiplication consumes a finite noise budget, growing the inherent cryptographic error embedded in the ciphertext. Polynomial approximations must balance degree against noise consumption:

• Higher-degree polynomials achieve better accuracy but consume more budget
• Rescaling in CKKS truncates noise after each multiplication
• Bootstrapping resets the budget when exhausted, enabling deep polynomial evaluations Efficient approximation minimizes the multiplicative depth required.

Single Instruction, Multiple Data encoding leverages the Chinese Remainder Theorem to pack thousands of plaintext values into a single ciphertext. Polynomial approximations are evaluated in parallel across all packed slots, amortizing computational cost. This is critical for ML inference where a single polynomial evaluation simultaneously processes:

• All neurons in a layer
• All samples in a batch
• All channels in a convolution

The Remez exchange algorithm is the gold standard for finding optimal polynomial approximations over a bounded interval. It minimizes the maximum absolute error (minimax approximation) between the target function and the polynomial. For FHE applications, Remez-optimized polynomials achieve the same accuracy as Taylor or Chebyshev expansions with lower degree, directly reducing multiplicative depth and noise consumption. This is critical for approximating sigmoid and Gaussian functions.