An OBDD-Based Technique for the Efficient Synthesis of Garbled Circuits

Secure Multi-party Computation (SMC) protocols are exploited to perform collaborative computation of a function between two or more parties while keeping the privacy of the private inputs and sharing the computed result only. The Garbled Circuit (GC) protocol, proposed by Yao, is one of the possible approaches to solve the SMC problem, based on the evaluation of the Boolean Circuit representing the given function. Recently, the question to improve efficiency in secure multi-party computation has gained much interest. One of the proposed techniques to increase the efficiency of the GC protocol is based on the reduction of the number of non-XOR gates in the Boolean circuit, since the evaluation of XOR gates have no cost for the execution of the whole protocol. The aim of this work is to define a post-processing procedure that, given an optimized GC, decreases the number of non-XOR gates by transforming some parts of the circuit. The strategy is based on the fact that some gates behave as XORs apart from one output and then, if that input never occurs, those gates can be replaced by a XOR without changing the output of the overall network. The technique we propose is based on the analysis of the GC by using Ordered Binary Decision Diagrams (OBDD) representation. We present the application of our technique to some standard circuits to show the effectiveness of our proposal.