BASALISC: Programmable Asynchronous Hardware Accelerator for BGV Fully Homomorphic Encryption

Fully Homomorphic Encryption (FHE) allows for secure computation on encrypted data. We present BASALISC, an architecture family of hardware accelerators that aims to substantially accelerate FHE computations in the cloud. BASALISC is the first to implement the BGV scheme supporting fully-packed bootstrapping - the noise removal capability necessary to support arbitrary-depth computation. We propose a generalized version of bootstrapping that can be implemented directly in our hardware, instantiated with Montgomery multipliers that save 46% in silicon area and 40% in power consumption compared to traditional approaches. BASALISC's four-layer memory hierarchy includes a two-dimensional conflict-free inner memory layer that enables 32 Tb/s radix-256 NTT computations without pipeline stalls. Our conflict-resolution permutation hardware is generalized and re-used to compute BGV automorphisms without throughput penalty. BASALISC also has a custom multiply-accumulate unit to accelerate BGV key switching. Both BASALISC's computation units and inner memory layers are designed in asynchronous logic, allowing them to run at different speeds to optimize each function. To evaluate BASALISC, we study its physical realizability, emulate and formally verify its core functional units, and we study its performance on a set of benchmarks. First, we evaluate a single iteration of logistic regression training over encrypted data - an application that translates to 513 bootstraps, 900K high-level, or 27B low-level BASALISC instructions - showing that BASALISC is only 3,500 times slower than an Intel Xeon-class processor running without data encryption. We also run an individual bootstrapping operation, for which we show a speedup of 4,000 times over HElib - a popular software FHE library.