FHE-MENNs: Opportunities and Pitfalls for Accelerating Fully Homomorphic Private Inference with Multi-Exit Neural Networks

With concerns about data privacy growing in a connected world, cryptography researchers have focused on fully homomorphic encryption (FHE) for promising machine learning as a service solutions. Recent advancements have lowered the computational cost by several orders of magnitude, but the latency of fully homomorphic neural networks remains a barrier to adoption. This work proposes using multi-exit neural networks (MENNs) to accelerate the FHE inference. MENNs are network architectures that provide several exit points along the depth of the network. This approach allows users to employ results from any exit and terminate the computation early, saving both time and power. First, this work weighs the latency, communication, accuracy, and computational resource benefits of running FHE-based MENN inference. We show FHE-MENNs improvement over single exit networks on the accuracy-latency Pareto frontier, achieving around 7% accuracy boost for similar latencies. Then, we present the TorMENNt attack that can exploit the user's early termination decision to launch a concrete side-channel on both plaintext and FHE encrypted MENNs. In particular, we show that this attack leaks less than one bit per image per exit, and we demonstrate that TorMENNt can still infer private classification outputs. Results on a single CIFAR-10 image show that TorMENNt doubles an attacker's likelihood of correctly predicting the user's image class compared to random guessing, and on a batch of 100 images can achieve up to 68% prediction accuracy. We discuss possible countermeasures to mitigate the attack and examine their effectiveness. Finally, we tie the privacy risks with a cost-benefit analysis to obtain a practical roadmap for FHE-based MENN adoption.