TL;DR
Falcon is a novel framework that significantly accelerates secure neural network inference by performing computations in the frequency (spectral) domain. By replacing expensive homomorphic "rotation" operations with efficient spectral multiplications, Falcon reduces inference latency by 45% to 85% compared to previous state-of-the-art methods while maintaining high accuracy.
What Problem Does This Paper Address?
Machine Learning as a Service (MLaaS) allows users to run data through powerful models in the cloud. However, privacy is a major concern: users naturally hesitate to send sensitive data—like medical records or private photos—in plaintext. Homomorphic Encryption (HE) is a promising solution that allows a server to process encrypted data without ever decrypting it, ensuring the client's privacy is preserved.
The catch? HE is notoriously slow and computationally heavy. In modern HE systems, data is "packed" into large polynomials to allow for parallel processing (SIMD). While this packing makes element-wise operations efficient, it introduces a major bottleneck when aggregating data.
To perform a simple dot product or sum elements within an encrypted vector, the system must perform rotations to align the data slots. The authors observed that these rotations are roughly $10\times$ more expensive than standard multiplications between ciphertexts and plaintexts. Because standard neural network layers require massive amounts of accumulation, these rotations account for the vast majority of total inference time. Previous attempts to solve this either required the client to stay online to help with calculations (interactive) or suffered from massive "noise" growth that caused the encryption to fail.
Methods: The Spectral Shortcut
Falcon introduces a non-interactive, frequency-domain approach to eliminate the rotation bottleneck entirely. Its core components include:
- Homomorphic Discrete Fourier Transform (HDFT): Falcon utilizes a novel algorithm to convert encrypted spatial data into its frequency-domain representation directly on the server, without requiring the client to decrypt or assist.
- Block-Circulant Matrices: The authors represent neural network weights as block-circulant matrices.
This mathematical structure is the key to Falcon's speed. By moving to the spectral domain, the "summation" part of a convolution or dot product is essentially pre-calculated by the properties of the Fourier Transform. This allows both Convolutional (Conv) and Fully Connected (FC) layers to be computed as simple element-wise multiplications, bypassing the need for expensive rotations.
- Complex Number Encoding: Since the BFV encryption scheme used in the paper only supports integers, Falcon uses a specific quantization and encoding strategy to handle the complex numbers inherent in spectral analysis (real and imaginary parts) within the SIMD slots of the ciphertext.
- Noise Management: Every operation in HE adds a small amount of "noise" to the ciphertext. If the noise grows too large, the data is corrupted. The paper provides a detailed analysis of how spectral operations affect the "noise budget," ensuring that the final result can still be correctly decrypted by the client.
Key Insights and Ideas
- The "Rotation Tax": The most significant insight is identifying that rotations, not multiplications, are the primary obstacle to efficient HE-based inference.
- Universal Application: While previous "spectral" HE works focused only on convolutions, Falcon successfully applies the block-circulant matrix technique to Fully Connected layers, which often dominate the latency in deep networks.
- Non-interactive Efficiency: Falcon achieves its speedups without requiring the client to participate in the middle of the inference process, making it much more practical for real-world mobile or low-power devices.
Key Results
The authors evaluated Falcon on two standard benchmarks for secure inference: MNIST (70,000 handwritten digits) and CIFAR-10 (60,000 complex tiny images). Falcon demonstrates a massive leap in performance over previous baselines like LoLa, CHET, and EVA:
- Latency Reduction: Falcon reduced inference latency by 45.45% to 85.34% across different models.
- MNIST Performance: Falcon completed an inference in just 1.2 seconds, compared to LoLa's 2.2 seconds and CryptoNets' 205 seconds. Accuracy remained state-of-the-art at 98.95%.
- CIFAR-10 Performance: On the more challenging CIFAR-10 dataset, Falcon achieved an inference time of 107 seconds, a massive improvement over LoLa's 730 seconds, while maintaining an accuracy of 76.5%.
Limitations and Future Work
- Activation Functions: Like most HE-based networks, Falcon cannot easily compute non-linear functions like ReLU. It relies on approximating these with a square function ($x^2$), which can limit the depth and expressiveness of the neural network.
- Noise Growth: While Falcon manages noise effectively, the HDFT and HIDFT operations still consume a significant portion of the noise budget. Future work could look into even more noise-efficient spectral transforms.
- Absolute Latency: While 107 seconds for a CIFAR-10 image is a "fast" result for Homomorphic Encryption, it is still orders of magnitude slower than plaintext inference (which takes milliseconds). Further hardware acceleration or algorithmic breakthroughs are needed for real-time applications.
Summary updated