PAPER: Privacy-Preserving Convolutional Neural Networks using Low-Degree Polynomial Approximations and Structural Optimizations on Leveled FHE

Technical Summary: Privacy-Preserving CNNs using Low-Degree Polynomial Approximations and Structural Optimizations

1. Problem Statement

The paper addresses the efficiency and accuracy bottlenecks in non-interactive Privacy-Preserving Machine Learning (PPML) using Fully Homomorphic Encryption (FHE). While FHE allows for inference on encrypted data without client interaction, current methods face two major hurdles:

• Performance Bottleneck: Existing deep CNNs rely heavily on bootstrapping—a computationally expensive FHE operation used to reset the noise/level of ciphertexts—to handle the high multiplicative depth required by deep architectures.
• Accuracy Gap: Because FHE natively supports only polynomial operations, non-linear activation functions (like ReLU) must be approximated by high-degree polynomials. These approximations increase multiplicative depth and typically cause a 2–5% drop in accuracy compared to plaintext models due to "escaping activations" (values drifting outside the approximation range) and "coefficient truncation" (precision loss in fixed-point arithmetic).

2. Methodology

The authors propose a holistic optimization framework designed to run deep CNNs (like ResNet-32) entirely under Leveled FHE (LFHE), thereby eliminating the need for bootstrapping. Their approach is divided into four pillars:

A. Low-Degree Polynomial Training (The "PAPER" Strategy):

• Quadratic Approximations: They use degree-2 polynomials for ReLU, which achieves the theoretical minimum multiplicative depth of one.
• Quantization-Aware Fitting: To prevent coefficient truncation, they use an integer least-squares approach during the polynomial fitting process.
• Regularization & Clipping: To solve the "escaping activation" problem, they introduce a layer-wise clip-range penalty in the loss function and use pre-activation clipping during training to ensure intermediate values stay within the polynomial's valid approximation interval. They also employ a warm-up schedule for the regularization strength to ensure training stability.

B. Structural Optimizations:

• Node Fusing: Merges consecutive layers (e.g., Batch Normalization + Activation or Convolution + Batch Normalization) into single, functionally equivalent polynomial nodes to reduce the total number of operations and depth.
• Weight Redistribution: A technique that redistributes weights between "donor" nodes (like average pooling or polynomial activations) and "receiver" nodes (like convolutions) to normalize coefficients to one, effectively reducing the multiplicative depth of specific layers.
• Tower Reuse: An inference-time optimization that allows multiple multiplications to occur within the same FHE level by utilizing sublevels within the RNS moduli, reducing the total number of required rescaling operations.

C. Co-design & Data Layout:

• Ensemble Inference: To recover accuracy lost to low-degree approximations, they use an ensemble of multiple independently trained models. They exploit unused ciphertext slots in the HW data layout to pack these models into a single homomorphic evaluation.
• Slice Clustering: To prevent the ensemble from becoming computationally prohibitive, they introduce a clustering technique. Instead of clustering the whole model, they cluster weights within "slices" (vertical strips of the kernel) and use a shared codebook across all ensemble members. This allows multiple models to share the same plaintext encodings.

3. Key Contributions

1. First successful training of deep CNNs with degree-2 polynomials that achieves accuracy comparable to plaintext ReLU.
2. A suite of structural optimizations that reduces the required FHE levels by a factor of five compared to prior work.
3. A novel ensemble-clustering strategy that enables high-accuracy inference without increasing the number of homomorphic multiplications.
4. Demonstration of deep CNNs (ResNet-32) running entirely under LFHE without the need for bootstrapping.

4. Results

The authors evaluated their method on CIFAR and Tiny-ImageNet datasets using VGG and ResNet architectures:

• Accuracy: The "PAPER" method closes the accuracy gap, achieving results comparable to (and in some cases, slightly exceeding) plaintext ReLU models. It significantly outperforms the previous state-of-the-art (PILLAR) in both stability and accuracy.
• Speed: The approach achieves up to 4× faster private inference than existing non-interactive methods.
• Efficiency: By reducing the multiplicative depth, they significantly lowered the number of RNS levels required (e.g., for ResNet-32, reducing levels from 157 in prior work to 32).

5. Significance

This work shifts the paradigm of FHE-based machine learning from "compensating for inefficiency with bootstrapping" to "minimizing depth through architectural and mathematical optimization." By proving that modern, deep CNNs are compatible with Leveled FHE, the paper paves the way for deploying highly accurate, high-performance, and privacy-preserving AI services in real-world industries (such as medical or financial sectors) where data confidentiality is paramount and client-side resources are limited.