Toward Design of Garbled Circuits Using Quantum Gates

Abstract—Two-party Secure Multi-party Computation (SMC) is a classical problem in theoretical security. The Garbled Circuit (GC) approach has been proposed as a method for solving SMC using Boolean circuits. Actually, interest has grown in the efficiency of this technique and in its applications to computation outsourcing in untrusted environments. A recent work shows that EXOR gates in a Boolean circuit have no cost for the secure computation protocol. Therefore, circuits with a reduced number of non-EXOR gates are more convenient. In this work, we discuss Garbled Circuit construction for two-party secure function evaluation using quantum gates (QG). We observe that, in some cases, the quantumGCinvolves a lower number of non-EXOR gates than the corresponding classical GC implementations, resulting in a reduced cost in terms of Oblivious Transfer (OT) communication at run time.