  FHE offers protection to private data on third-party cloud servers by
allowing computations on the data in encrypted form. However, to support
general-purpose encrypted computations, all existing FHE schemes require an
expensive operation known as bootstrapping. Unfortunately, the computation cost
and the memory bandwidth required for bootstrapping add significant overhead to
FHE-based computations, limiting the practical use of FHE. In this work, we
propose FAB, an FPGA-based accelerator for bootstrappable FHE. Prior FPGA-based
FHE accelerators have proposed hardware acceleration of basic FHE primitives
for impractical parameter sets without support for bootstrapping. FAB, for the
first time ever, accelerates bootstrapping (along with basic FHE primitives) on
an FPGA for a secure and practical parameter set. The key contribution of our
work is to architect a balanced FAB design, which is not memory bound. To this
end, we leverage recent algorithms for bootstrapping while being cognizant of
the compute and memory constraints of our FPGA. We use a minimal number of
functional units for computing, operate at a low frequency, leverage high data
rates to and from main memory, utilize the limited on-chip memory effectively,
and perform operation scheduling carefully. For bootstrapping a fully-packed
ciphertext, while operating at 300 MHz, FAB outperforms existing
state-of-the-art CPU and GPU implementations by 213x and 1.5x respectively. Our
target FHE application is training a logistic regression model over encrypted
data. For logistic regression model training scaled to 8 FPGAs on the cloud,
FAB outperforms a CPU and GPU by 456x and 6.5x and provides competitive
performance when compared to the state-of-the-art ASIC design at a fraction of
the cost.
