Polynomial Approximation

A foundational method that minimizes the squared error between the target non-linear function and a polynomial over a defined interval.

• Mechanism: Solves for polynomial coefficients that minimize the integral of the squared difference.
• Best for: Approximating smooth functions like sigmoid or tanh where average-case error matters.
• Trade-off: May exhibit Runge's phenomenon at interval boundaries, causing large edge errors.
• Example: Approximating sigmoid on [-5, 5] with a degree-7 polynomial.

Uses the Remez algorithm to find the polynomial that minimizes the maximum absolute error over the target interval.

• Mechanism: Iteratively adjusts coefficients to achieve an equioscillation property.
• Best for: Approximating ReLU or sign functions where worst-case error must be bounded.
• Advantage: Guarantees uniform error bounds across the entire domain.
• Example: A degree-3 minimax approximation of ReLU on [-1, 1] ensures no point exceeds a specified error threshold.

Constructs an approximating polynomial by interpolating the target function at the roots of Chebyshev polynomials.

• Mechanism: Selects interpolation nodes clustered near interval edges to suppress Runge's phenomenon.
• Best for: Near-optimal uniform approximation with simple construction.
• Advantage: Provides a close proxy to minimax results without iterative Remez computation.
• Example: Interpolating the swish activation at Chebyshev nodes for stable encrypted inference.

A local approximation method using derivatives at a single point to construct a power series.

• Mechanism: Expands the function around a center point using its derivatives.
• Best for: High accuracy very close to the expansion point.
• Limitation: Error grows rapidly away from the center; rarely used alone for wide-interval HE inference.
• Example: Approximating exp(x) near x=0 for softmax components in encrypted attention mechanisms.

Divides the input domain into segments and fits a separate low-degree polynomial to each segment.

• Mechanism: Combines interval partitioning with local approximation.
• Best for: Functions with sharp transitions like ReLU or leaky ReLU.
• Implementation: Requires homomorphic multiplexing to select the correct polynomial based on encrypted input sign.
• Example: Using a degree-2 polynomial for negative inputs and a linear identity for positive inputs to approximate ReLU.

Approximates a complex function by composing simpler, individually approximated sub-functions.

• Mechanism: Breaks the target into a chain of operations, each replaced by a polynomial.
• Best for: Functions like GELU or swish that combine multiplication with smooth activation.
• Advantage: Reduces the total multiplicative depth compared to a single high-degree fit.
• Example: Approximating GELU by composing a polynomial for the Gaussian CDF with the identity function x.

Every homomorphic multiplication consumes noise budget and increases ciphertext size. Polynomial approximation directly impacts this budget:

• Higher-degree polynomials consume more multiplicative depth
• Leveled FHE requires knowing the exact circuit depth before encryption
• Modulus switching and rescaling reduce noise but also reduce precision
• The goal is finding the lowest-degree polynomial that achieves acceptable model accuracy while fitting within the available noise budget

Polynomial approximation is often used in hybrid MPC-HE protocols to optimize end-to-end encrypted inference:

• Linear layers (matrix multiplications, convolutions) are evaluated efficiently using HE with SIMD packing
• Non-linear activations are evaluated using MPC protocols, avoiding polynomial approximation entirely
• This design pattern leverages the linear-operation efficiency of HE and the non-linear evaluation efficiency of MPC
• Trade-off: introduces communication rounds between parties but eliminates approximation error

Single Instruction Multiple Data parallelism dramatically improves the amortized throughput of polynomial evaluation:

• Multiple plaintext values are packed into a single ciphertext
• A single homomorphic addition or multiplication applies to all packed slots simultaneously
• Polynomial approximation of activation functions benefits from batch evaluation across many neurons
• Galois keys enable rotation of slots within a packed ciphertext, required for implementing convolution operations in the encrypted domain