FHEMIST: A Maximum Independent Set Technique for Efficient Bootstrapping Reductions in FHE Evaluations
Abstract
Fully Homomorphic Encryption (FHE) enables arbitrary computation over encrypted data but suffers from noise growth, which eventually causes ciphertexts to be undecryptable after a few computations. Bootstrapping mitigates this issue but incurs significant computational overhead. Torus-FHE (TFHE) scheme [JoC 2019] achieves comparatively fast bootstrapping (9–10 ms per binary gate) relative to BGV and CKKS; however, its requirement of bootstrapping after every gate makes large Boolean circuits computationally expensive, necessitating circuit-level optimizations to reduce gate count and enhancing the efficiency of encrypted computation. In this work, we introduce a novel circuit optimization technique based on the graph-theoretic notion of the Maximum Independent Set (MIS), defined as a set of mutually non-adjacent vertices of maximum cardinality. Our approach begins by transforming Boolean circuits into directed acyclic graphs (DAGs), after which we compute an MIS under a modified formulation tailored to the characteristics of TFHE gate evaluation. Specifically, we refine the standard notion of non-adjacency by introducing additional dependency constraints-- two nodes are treated as dependent, and hence cannot simultaneously belong to the independent set, if they share a common output node. This modification is crucial for preserving the correctness of encrypted computation under TFHE. We further utilize the observation from the prior work [Singh et al., AsiaCCS 2025], which shows that two consecutive binary gates in TFHE can be evaluated using a single bootstrapping operation. Building on this insight, we exploit independence within the MIS to selectively disable redundant bootstrapping steps. Therefore, the maximality of the set ensures a near-optimal reduction in the number of required bootstrapping operations. However, computing an MIS for large-scale graphs is computationally expensive. To address this, we develop a GPU-accelerated approach based on a Maximum Cut formulation for scalable computation. Our Experimental results demonstrate up to more than 30% reduction in bootstrapping operations over the baseline and a 10-15% reduction over state-of-the-art methods; for example, our optimized AES-128 circuit achieves a run-time of around 268 secs compared to the state-of-the-art that achieves around 290 secs, where the baseline is 367 secs. This leads to a substantial performance improvement for practical FHE applications.