Cut Tracing with E-Graphs for Boolean FHE Circuit Synthesis Conference: ; June 2025; Seoul, South Korea
Julien de Castelnau, Mingfei Yu, Giovanni De Micheli · 2025
Read Cut Tracing with E-Graphs for Boolean FHE Circuit Synthesis Conference: ; June 2025; Seoul, South Korea by Julien de Castelnau, Mingfei Yu, Giovanni De Micheli (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2506-12883.txt.
Introduction
Julien de Castelnau, Mingfei Yu, and Giovanni De Micheli speed up circuits that compute on encrypted data. Their 2025 paper works in fully homomorphic encryption, a method that lets servers calculate without ever seeing the raw values, but at heavy cost in running time.
Two measures drive that cost: how many multiplications a circuit holds in total, and how many stack along its longest path. Cutting one tends to swell the other, and past tools chased them one at a time. The team uses e-graphs, a structure that holds many equal forms of a circuit at once, to trace cuts and blend two leading flows. Early tests cut evaluation time by up to forty percent.
Catalog record
| CREATOR | Julien de Castelnau, Mingfei Yu, Giovanni De Micheli |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 28 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2506-12883
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Cut Tracing with E-Graphs for Boolean FHE Circuit Synthesis Conference: ; June 2025; Seoul, South Korea Julien de Castelnau, Mingfei Yu, Giovanni De Micheli Abstract . Fully Homomorphic Encryption (FHE) is a promising privacy-preserving technology enabling secure computation over encrypted data. A major limitation of current FHE schemes is their high runtime overhead. As a result, automatic optimization of circuits describing FHE computation has garnered significant attention in the logic synthesis community. Existing works primarily target the multiplicative depth (MD) and multiplicative complexity (MC) of FHE circuits, corresponding to the total number of multiplications and maximum number of multiplications in a path from primary input to output, respectively. In many FHE schemes, these metrics are the primary contributors to the homomorphic evaluation runtime of a circuit. However, oftentimes they are opposed: reducing either depth or complexity may result in an increase in the other. To our knowledge, existing works have yet to optimize FHE circuits for overall runtime, only considering one metric at a time and thus making significant tradeoffs. In this paper, we use e-graphs to augment existing flows that individually optimize MC and MD, in a technique called cut tracing . We show how cut tracing can effectively combine two state-of-the-art MC and MD reduction flows and balance their weaknesses to minimize runtime. Our preliminary results demonstrate that cut tracing yields up to a 40% improvement in homomorphic evaluation runtime when applied to these two flows. 1. Introduction An FHE circuit is a DAG that describes computations on ciphertexts with the main operations of FHE, homomorphic add and multiply. Figure 1 shows an example circuit computing the expression (x_{1}\times x_{2})\times(x_{1}+x_{2}) , where x_{1} and x_{2} are ciphertexts. The plaintext message encoded in the ciphertext is assumed to be an integer mod some p , termed the plaintext modulus . When p=2 , homomorphic add and multiply operations are equivalent to XOR and AND gates on Booleans. In this case, an FHE circuit is equivalent to an XOR-AND graph (XAG). We focus on the Boolean case in this work, because many FHE applications, such as a CRC check, rely on a bitwise integer encoding ( Gouert et al. 2023 ) . x_{1} x_{2} \times + \times Figure 1 . The expression (x_{1}\times x_{2})\times(x_{1}+x_{2}) as an FHE circuit. x_{1} and x_{2} are ciphertexts and \times , + correspond to homomorphic multiply and add, respectively. The limiting factor in most FHE schemes is the runtime overhead of multiplication, with addition being comparatively cheap. Therefore, when considering an FHE circuit, the total number of multiplications, the MC, is a major performance indicator. However, multiplications also have a disparate impact on the noise budget of the ciphertext, in comparison to addition. FHE schemes store a noise component in ciphertexts as part of a ring learning with errors (RLWE) construction, used to provide their security guarantees. Every operation on the ciphertext increases its noise; if the noise grows past a certain budget, decryption will fail. While it is possible to reset the noise on a ciphertext in a procedure known as bootstrapping , it is often prohibitively time-consuming. Instead, the ciphertext size can be increased, raising the relative noise budget, at the cost of increasing the global overhead of all operations. From this, the constraint of multiplicative depth (MD) emerges: as each multiplication operation scales the noise quadratically, the longest path of multiplications in sequence in the circuit dictates the allocated noise budget, in turn increasing the global runtime cost. There is a rich body of work on automatic methods to reduce the MD and MC of Boolean circuits ( Carpov et al. 2017 ; Lee et al. 2020 ; Häner and Soeken 2022 ; Testa et al. 2020 ) . For example, ( Lee et al. 2020 ) uses program synthesis to learn a set of MD-optimal circuit rewrite rules, applying them towards a set of HE benchmarks to reduce their evaluation runtime. Likewise, ( Testa et al. 2020 ) presents a flow for MC reduction using a combination of area-reducing logic synthesis techniques. However, to our knowledge, the joint optimization of both MC and MD in the context of FHE has not been addressed. Existing techniques only consider one quantity at a time, often blowing up MC in the process of reducing MD, or vice versa. These techniques are difficult to extend to a model of overall HE cost that balances MC and MD for two reasons. First, they all apply optimizations locally, relying on the computation of some local gain. When both MD and MC are incorporated, gain becomes a poor indicator of the global cost that will be achieved. Second, they apply these optimizations as destructive rewrites to the circuit, meaning they compose poorly: alternating MD and MC optimization passes does not work because the design gets stuck in a local minimum prioritizing only one metric. Equality saturation has been shown to be effective in situations like these, where destructive, greedy rewriting leads to a poor global cost. However, we observe empirically that equality saturation struggles to scale with the demands of FHE circuit optimization, often producing considerably worse results than state-of-the-art greedy methods. In particular, we find that the equivalence information generated in the e-graph by saturation, does not consistently lead to better solutions during extraction. For MD (which admits efficient optimal extraction), saturation fails to find solutions identified by simpler greedy approaches. Furthermore, the e-graph sizes generated by saturation make the use of optimal MC extraction methods, like those based on ILP, impractical or prohibitive to apply. Instead, we introduce a method we call “cut tracing”, which uses e-graphs to store the intermediate optimizations found by existing MD and MC reduction algorithms. Cut tracing is able to strike a balance between the tendency of these algorithms to fall into local minima and the inefficiency of equality saturation for problems of this scale. Compared to equality saturation in particular, cut tracing produces e-graphs small enough that we not only gain the ability to use an ILP formulation for MC-optimal extraction, but to add MD constraints to the formulation, allowing us to sweep the design space of MD/MC tradeoffs. In this paper, we motivate and discuss cut tracing with e-graphs as a means to optimize Boolean FHE circuits. We use a flow combining the state-of-the-art MD and MC algorithms ESOP balancing and MC-oriented cut rewriting and resubstitution ( Häner and Soeken 2022 ; Testa et al. 2020 ) as our baseline, showing how cut tracing can augment this flow to minimize the overall HE runtime of a suite of benchmarks. 2. Background 2.1. XOR-AND graphs As mentioned, in the case of a Boolean plaintext space, an FHE circuit is equivalent to a XOR-AND graph (XAG). We define an XAG as a directed acyclic graph with nodes V and edges E . An edge e=(v,v_{i})\in E corresponds to a fanin v_{i} for the gate v . We define the set of primary inputs PI=\{v\in V|\forall v_{i},(v,v_{i})\notin E\} , and primary outputs PO=\{v\in V|\forall v_{o},(v_{o},v)\notin E\} . The nodes in V-PI correspond to the 2-input gates \wedge and \oplus . Next, we define a function d(v) where d(v)=1 if v\in V is a multiplication, and d(v)=0 otherwise. Then, the multiplicative depth (MD)