Accelerating the Uncomputable: A Custom FPGA Core for Homomorphic Encryption

Executive Summary

TL;DR: This paper presents a specialized hardware co-processor on a Virtex-7 FPGA designed to smash the performance barriers of Somewhat Homomorphic Encryption (SHE). By focusing on the most expensive operation—large-degree polynomial multiplication—the authors achieved a 102x speedup over CPU implementations, bringing complex tasks like homomorphic AES evaluation down to the sub-second range.

Positioning: This work is a pivotal "system-level" contribution. Rather than proposing a new cryptosystem, it focuses on the practical engineering required to move NTRU-based encryption from theoretical interest to functional reality using FPGA-based parallelism.

Problem & Motivation: The "Homomorphic Tax"

Fully Homomorphic Encryption (FHE) is the "Holy Grail" of cryptography, allowing servers to process encrypted data without ever seeing the raw content. However, this comes at a massive cost. Prior to this work:

• Evaluating an AES circuit homomorphically could take 36 hours.
• The primary bottleneck is performing multiplications of polynomials with degrees as large as $2^{15}$ and coefficients spanning hundreds of bits.
• Software is inherently sequential and struggles with the massive memory bandwidth required for these operations.

The authors recognized that to make FHE usable, we must move away from general-purpose CPUs and toward Spatially Computed Architectures (FPGAs/ASICs) that can handle the massive parallelism of the Number Theoretic Transform (NTT).

Methodology: The Arithmetic Engine

The core of the solution is a hardware-optimized NTT-based Multiplier. Instead of $O(N^2)$ complexity, the NTT allows for $O(N\log N)$ performance.

1. The Strategy: CRT + NTT

To handle polynomials with massive coefficients (e.g., 1271 bits for AES), the authors used the Chinese Remainder Theorem (CRT). This breaks one "giant" polynomial into many "small" polynomials (32-bit coefficients). These small polynomials are then processed in parallel on the FPGA using NTT.

2. Hardware Architecture

The architecture utilizes a distributed memory model to feed 256 modular multipliers simultaneously.

• Modular Arithmetic: They implemented a custom 32-bit modular multiplier using Barrett Reduction, specifically designed to fit into the FPGA's DSP48E1 slices.
• The Butterfly Unit: A pipelined Cooley-Tukey architecture processes the NTT stages.

Fig 1: The iterative NTT circuit showing the butterfly structure and twiddle factor application.

Experiments & Results

The design was implemented on a Xilinx Virtex-7 XC7VX690T. The gains were transformative:

• Polynomial Multiplication (N=32,768): The FPGA handles this in roughly 6.25 ms.
• Cipher Evaluation:
  • AES: Amortized per block time of 442 ms.
  • Prince: Amortized per block time of 52 ms.

Fig 2: Comparison showing the FPGA accelerator (Ours) achieving 181x speedup in Relinearization compared to CPU.

The study also candidly addresses the PCIe Bottleneck. As the computation on the FPGA becomes faster, the time to move encrypted data across the PCIe bus becomes a significant portion of the total latency (approx. 3.25 ms for AES-related transfers).

Critical Analysis & Conclusion

Takeaway

The paper proves that the bottleneck of FHE isn't just "math"—it's data movement and arithmetic density. By using CRT to parallelize the workforce and NTT to reduce algorithmic complexity, they achieved a leap that software cannot replicate.

Limitations

• Memory Bound: The design is limited by the number of Block RAMs on the FPGA. Higher degrees ($2^{16}+$) or larger coefficient sets would require off-chip DDR memory, which would introduce significant latency.
• PCIe Overhead: For shallow circuits, the cost of moving data to the FPGA might outweigh the benefits.

Future Outlook

This work sets the stage for "FHE on a Chip." Future iterations could integrate the CRT conversion directly into the hardware to further reduce the burden on the host CPU. As FHE moves toward cloud privacy, such accelerators will likely become standard in data center server racks alongside GPUs.