Skip to content
Book Open access

FHEMIST: A Maximum Independent Set Technique for Efficient Bootstrapping Reductions in FHE Evaluations

Nov 2026 · Proceedings of the 2026 ACM SIGSAC Conference on Computer and Communications Security · 0 citations · 19 references

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.

Read PDF

We use cookies to run the site and, with your consent, for analytics and to show ads. See our Cookie Policy.