Paper 2026/363

LazyArc: Dynamic Out-of-Order Engine for High-Throughput FHE

Abstract

Fully Homomorphic Encryption (FHE) is a modern cryptographic technique that allows performing computations directly on encrypted data. This makes FHE an indispensable method for privacy-preserving applications, where users' data are encrypted and processed by a potentially untrusted third party. Nevertheless, FHE operations are computationally expensive, often rendering them impractical for realistic scenarios. Notably, a major performance bottleneck for FHE is an operation called bootstrapping that allows refreshing the inherent noise of FHE data to support more computations. In this work, we introduce LazyArc, a versatile lightweight dynamic Out-of-Order (OoO) engine that supports higher-throughput FHE computations. Our proposed OoO paradigm improves the performance by masking the latency of bootstrapping via a bespoke instruction-bootstrapping scheduling paradigm. Also, we introduce a novel tool, dubbed RegisterMap Tool, to statically analyze FHE arithmetic circuits and track the noise of each ciphertext to allow proactive bootstrapping scheduling. Our approach is evaluated using linear algebra benchmarks and achieves about 1.20$\times$ speedup compared to in-order baselines, up to about 1.73$\times$ speedup compared to the FHEBooster scheduler, and about 8.74$\times$ compared to the PulpFHE architecture.