Striving for Both Quality and Speed: Logic Synthesis for Practical Garbled Circuits

Garbled circuit (GC) is one of the few promising protocols to realize general-purpose secure computation. The target computation is represented by a Boolean circuit that is subsequently transformed into a network of encrypted tables for execution. The need of distributing GCs among parties however requires excessive data communication, called garbling cost, which bottlenecks system performance. Due to the zero garbling cost of XOR operations, existing works reduce garbling cost by representing the target computation as the XOR-AND graph (XAG) with minimum multiplicative complexity. Recently, an XOR-OneHot graph (X1G) has been proposed as an efficient GC representation. However, there is a lack of formal proof of X1G performance in the literature. In this paper, we prove that starting from any XAG, there exists an X1G implementation with equal or lower garbling cost. Based on our findings, we propose (a) an affine function classification-based database generation method, which decouples time-consuming on-the-fly exact syn-thesis from Boolean rewriting; (b) a novel optimal X1G synthesis approach to accelerate the database generation procedure. The proposals jointly facilitate a performant Boolean rewriting-based X1G optimization method. Experimental evaluations show significant improvement in both garbling cost and runtime: with a 2273.63× speed-up achieved on average, the proposed method realized an up-to 8.20% improvement in garbling cost reduction compared to the state-of-the-art.