International Association
for Cryptologic Research

Optimizing Boolean circuits presents a considerable challenge, especially when aiming to construct circuits amenable to Fully Homomorphic Encryption (FHE) schemes. FHE enables arbitrary computations on encrypted data but incorporates a computationally intensive operation called bootstrapping, necessary for reducing noise in ciphertexts to facilitate computations on circuits of arbitrary depth. This operation can consume a substantial amount of time, depending on the size of the circuits. To address this issue, we propose a technique for efficiently synthesizing circuits specific to FHE by utilizing multi-input homogeneous and composite Boolean gates. Following this we develop an automated framework for designing efficient circuits compatible with FHE schemes. In this work, we use Torus-FHE (TFHE) (JoC 2019), a widely used FHE scheme for Boolean circuits due to its fast bootstrapping operation per bit. Existing techniques typically employ either multi-input homogeneous gates or, multi-bit Look-Up tables during circuit synthesis, which often limits their ability to produce highly optimized circuits for FHE. Our approach addresses this limitation by proposing viable multi-input composite gates alongwith the homogeneous gates during circuit synthesis. Additionally, we propose an efficient and lightweight circuit synthesis approach based on graph optimization. Our approach identifies convex sub-graphs in a Directed Acyclic Graph (DAG) representing the input circuit and replaces them with a more compact structure. This results in a reduction of the number of nodes in the DAG and so as the number of Boolean gates in the input circuit. Our proposed framework provides the most efficient Boolean circuits for TFHE till date, achieving up to a 20% improvement in homomorphic evaluation time compared to the state-of-the-art general compiler optimization techniques for TFHE, and it also demonstrates a 4-6× improvement over prior work on FHEW-like schemes.