Introduction
Machine Learning as a Service (MLaaS) offers immense computational power for tasks like medical diagnosis and financial forecasting, but it introduces significant privacy risks when raw data is sent to the cloud. Homomorphic Encryption (HE) provides a potential solution by allowing servers to process data while it remains encrypted. However, standard HE schemes are mathematically restricted to additions and multiplications, necessitating error-prone polynomial approximations for non-linear functions like ReLU activations and Max Pooling. These approximations lead to "distribution distortion" and severe accuracy degradation as networks grow deeper.
SHE (Shift-accumulation-based Homomorphic Encryption) is a novel framework designed to overcome these bottlenecks. By leveraging the bit-level flexibility of the TFHE cryptosystem and logarithmic data representation, SHE eliminates the need for polynomial approximations, reducing latency by up to 94% while maintaining state-of-the-art accuracy.
Methodology
SHE introduces three key innovations to enable deep, accurate, and fast privacy-preserving inferences:
1. Exact Non-linearities via TFHE
Instead of using low-degree polynomial approximations (e.g., $x^2$), SHE utilizes Leveled Fast Homomorphic Encryption over Torus (LTFHE). Because TFHE can efficiently implement Boolean gates (AND, OR, MUX) on encrypted bits, the authors designed custom circuits to implement exact ReLU and Max Pooling operations, preventing the compounding errors found in prior HE-enabled models.
2. Logarithmic Quantization
Homomorphic multiplications are computationally expensive and the primary source of latency. SHE quantizes network weights to their nearest power-of-2 representations ($2^k$), allowing the server to replace slow multiplications with much faster homomorphic bit-shifts.
3. Mixed Bitwidth Accumulator
The computing cost of an encrypted adder is proportional to its bitwidth. SHE employs a "mixed bitwidth" adder tree that uses smaller bitwidths at the lower levels and increases them only as needed, minimizing computational overhead without sacrificing precision.
Key Results
SHE was evaluated on diverse benchmarks, including MNIST, CIFAR-10, ImageNet, and medical imaging datasets. It represents a significant leap in performance compared to prior state-of-the-art models like CryptoNet (CNT) and Faster CryptoNet (FCN).
- Accuracy: On MNIST, SHE achieves 99.77% accuracy. On CIFAR-10, it reaches 94.62%, a massive improvement over the ~76% seen in prior polynomial-based models.
- Latency: SHE reduces inference latency by 76.21% to 94.23%. An MNIST inference that previously took hundreds of seconds can be completed in roughly 9 seconds.
- Scalability: SHE is the first HE-enabled model to support deep CNNs on ImageNet and recurrent architectures (LSTMs) for language modeling.
Discussion and Limitations
While SHE is a major step forward, challenges remain. Encrypted data is significantly larger than plaintext; a single MNIST image expands to 122.5 MB when encrypted, creating high communication overhead. Furthermore, while SHE is 10-20x faster than previous HE methods, it remains orders of magnitude slower than unencrypted inference. Future work may involve optimizing the TFHE bootstrapping process and exploring hardware acceleration via FPGAs or ASICs to further bridge the performance gap.
Summary updated