  Homomorphic Encryption (HE) is one of the most promising post-quantum
cryptographic schemes that enable privacy-preserving computation on servers.
However, noise accumulates as we perform operations on HE-encrypted data,
restricting the number of possible operations. Fully HE (FHE) removes this
restriction by introducing the bootstrapping operation, which refreshes the
data; however, FHE schemes are highly memory-bound. Bootstrapping, in
particular, requires loading GBs of evaluation keys and plaintexts from
off-chip memory, which makes FHE acceleration fundamentally bottlenecked by the
off-chip memory bandwidth.
  In this paper, we propose ARK, an Accelerator for FHE with Runtime data
generation and inter-operation Key reuse. ARK enables practical FHE workloads
with a novel algorithm-architecture co-design to accelerate bootstrapping. We
first eliminate the off-chip memory bandwidth bottleneck through runtime data
generation and inter-operation key reuse. This approach enables ARK to fully
exploit on-chip memory by substantially reducing the size of the working set.
On top of such algorithmic enhancements, we build ARK microarchitecture that
minimizes on-chip data movement through an efficient, alternating data
distribution policy based on the data access patterns and a streamlined
dataflow organization of the tailored functional units -- including base
conversion, number-theoretic transform, and automorphism units. Overall, our
co-design effectively handles the heavy computation and data movement overheads
of FHE, drastically reducing the cost of HE operations, including
bootstrapping.
