TY - GEN
T1 - An OBDD-Based Technique for the Efficient Synthesis of Garbled Circuits
AU - Cimato, Stelvio
AU - Ciriani, Valentina
AU - Damiani, Ernesto
AU - Ehsanpour, Maryam
N1 - Publisher Copyright:
© Springer Nature Switzerland AG 2019.
PY - 2019
Y1 - 2019
N2 - 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.
AB - 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.
UR - http://www.scopus.com/inward/record.url?scp=85075599047&partnerID=8YFLogxK
U2 - 10.1007/978-3-030-31511-5_10
DO - 10.1007/978-3-030-31511-5_10
M3 - Conference contribution
AN - SCOPUS:85075599047
SN - 9783030315108
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 158
EP - 167
BT - Security and Trust Management - 15th International Workshop, STM 2019, Proceedings
A2 - Mauw, Sjouke
A2 - Conti, Mauro
PB - Springer
T2 - 15th International Workshop on Security and Trust Management, STM 2019 held in conjunction with the 24th European Symposium on Research in Computer Security, ESORICS 2019
Y2 - 26 September 2019 through 27 September 2019
ER -