Osiris: A Systolic Approach to Accelerating Fully Homomorphic Encryption

In this paper we demonstrate how fully homomorphic encryption (FHE) can be accelerated using a systolic-inspired architecture. We start by analyzing FHE algorithms and then design dedicated systolic or systolic-esque units for each major kernel. Connecting these units is challenging due to opposing data access patterns. We overcome this by developing a new data tiling approach, named limb interleaving. Here, data from independent residues (limbs) are fed to the units in a round-robin fashion rather than processing each limb to completion before the next. This choice creates a common data input-output pattern across kernels that allows the entire architecture, named Osiris, to operate in lockstep. The Osiris accelerator is systolic in nature. It comprises a set of simple processing cells (homogeneous within each unit), runs in lockstep, and omits many of the costly structures found in other architectures (e.g., register files, NoCs, and chaining). It is capable of processing key-switches, bootstrapping, and full neural network inferences with high utilization across a range of FHE parameters. To achieve high performance, we propose a new dataflow that efficiently maps state-of-the-art FHE matrix-vector products onto Osiris to promote reuse and parallelism. Our evaluation confirms that Osiris achieves performance on par with or exceeding previous state-of-the-art accelerators across all standard benchmarks.