AutoHoG: Automating Homomorphic Gate Design for Large-Scale Logic Circuit Evaluation

Recently, an emerging branch of research in the field of fully homomorphic encryption (FHE) attracts growing attention, where optimizations are carried out in developing fast and efficient homomorphic logic circuits. While existing works have pointed out that compound homomorphic gates can be constructed without incurring significant computational overheads, the exact theory and mechanism of homomorphic gate design have not yet been explored. In this work, we propose AutoHoG, an automated procedure for the generation of compound gates over FHE. We show that by formalizing the gate generation procedure, we can adopt a match-and-replace strategy to significantly improve the evaluation speed of logic circuits over FHE. In the experiment, we first show the effectiveness of AutoHoG through a set of benchmark gates. We then apply AutoHoG to optimize common Boolean tasks, including adders, multipliers, the ISCAS'85 benchmark circuits, and the ISCAS'89 benchmark circuits. We show that for various circuit benchmarks, we can achieve up to 5.7 x reduction in computational latency when compared to the state-of-the-art implementations of logic circuits using conventional gates.