Paper 2022/657

BASALISC: Programmable Asynchronous Hardware Accelerator for BGV Fully Homomorphic Encryption

Robin Geelen, KU Leuven
Michiel Van Beirendonck, KU Leuven
Hilder V. L. Pereira, KU Leuven
Brian Huffman, Galois (United States)
Tynan McAuley, Niobium Microsystems
Ben Selfridge, Galois (United States)
Daniel Wagner, Galois (United States)
Georgios Dimou, Niobium Microsystems
Ingrid Verbauwhede, KU Leuven
Frederik Vercauteren, KU Leuven
David W. Archer, Galois (United States)

Fully Homomorphic Encryption (FHE) allows for secure computation on encrypted data. Unfortunately, huge memory size, computational cost and bandwidth requirements limit its practically. 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 is a three-abstraction-layer RISC architecture, designed for a 1 GHz ASIC implementation and underway toward 150mm² die tape-out in a 12nm GF process. 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. The BASALISC toolchain comprises a custom compiler and a joint performance and correctness simulator. 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.

Available format(s)
Publication info
FHE BGV Hardware Accelerator ASIC
Contact author(s)
robin geelen1 @ kuleuven be
michiel vanbeirendonck @ kuleuven be
hildervitor limapereira @ kuleuven be
huffman @ galois com
tynan @ niobiummicrosystems com
benselfridge @ galois com
dmwit @ galois com
georgios @ niobiummicrosystems com
ingrid verbauwhede @ kuleuven be
frederik vercauteren @ kuleuven be
dwa @ galois com
2022-08-24: last of 2 revisions
2022-05-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Robin Geelen and Michiel Van Beirendonck and Hilder V. L. Pereira and Brian Huffman and Tynan McAuley and Ben Selfridge and Daniel Wagner and Georgios Dimou and Ingrid Verbauwhede and Frederik Vercauteren and David W. Archer},
      title = {BASALISC: Programmable Asynchronous Hardware Accelerator for BGV Fully Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2022/657},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.