  Fully Homomorphic Encryption (FHE) allows for the execution of computations
on encrypted data without the need to decrypt it first, offering significant
potential for privacy-preserving computational operations. Emerging
arithmetic-based FHE schemes (ar-FHE), like BGV, demonstrate even better
performance in word-wise comparison operations over non-arithmetic FHE (na-FHE)
schemes, such as TFHE, especially for basic tasks like comparing values,
finding maximums, and minimums. This shows the universality of ar-FHE in
effectively handling both arithmetic and non-arithmetic operations without the
expensive conversion between arithmetic and non-arithmetic FHEs. We refer to
universal arithmetic Fully Homomorphic Encryption as uFHE. The arithmetic
operations in uFHE remain consistent with those in the original arithmetic FHE,
which have seen significant acceleration. However, its non-arithmetic
comparison operations differ, are slow, and have not been as thoroughly studied
or accelerated. In this paper, we introduce BoostCom, a scheme designed to
speed up word-wise comparison operations, enhancing the efficiency of uFHE
systems. BoostCom involves a multi-prong optimizations including infrastructure
acceleration (Multi-level heterogeneous parallelization and GPU-related
improvements), and algorithm-aware optimizations (slot compaction, non-blocking
comparison semantic). Together, BoostCom achieves an end-to-end performance
improvement of more than an order of magnitude (11.1x faster) compared to the
state-of-the-art CPU-based uFHE systems, across various FHE parameters and
tasks.
