Secure Multi-party Computation (SMC) has been introduced to allow the computation of generic functions between two parties that want to keep secret the input they use, and share only the computed result. One of the approach proposed to solve the SMC problem relies on the design of Garbled Circuits (GC), that are Boolean circuits that can be evaluated collaboratively achieving the SMC goal. Recently, there is a growing interest on the efficiency of this technique and on its potential applications to computation outsourcing in untrusted environments. One of the possible ways to reduce the complexity of the computation is to lower the number of non-EXOR gates in the Boolean circuit, since those gates have no cost for the execution of the secure computation protocol. In this work, we discuss the possibility to construct Garbled Circuit using quantum gates (QG), observing that, in some cases, the quantum GC requires a lower number of non-EXOR gates with respect to the corresponding classical GC implementations, thus improving the overall efficiency of the execution of the SMC protocol.
Secure Multi-party Computation (SMC) has been introduced to allow the computation of generic functions between two parties that want to keep secret the input they use, and share only the computed result. One of the approach proposed to solve the SMC problem relies on the design of Garbled Circuits (GC), that are Boolean circuits that can be evaluated collaboratively achieving the SMC goal. Recently, there is a growing interest on the efficiency of this technique and on its potential applications to computation outsourcing in untrusted environments. One of the possible ways to reduce the complexity of the computation is to lower the number of non-EXOR gates in the Boolean circuit, since those gates have no cost for the execution of the secure computation protocol. In this work, we discuss the possibility to construct Garbled Circuit using quantum gates (QG), observing that, in some cases, the quantum GC requires a lower number of non-EXOR gates with respect to the corresponding classical GC implementations, thus improving the overall efficiency of the execution of the SMC protocol.
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 quantum GC involves 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 runtime.
Secure Multi-party Computation (SMC) is a classical problem in theoretical security. In a SMC problem, two or more parties must compute correctly a function f on their respective inputs x and y, while preserving the privacy of their inputs and additional security properties. One of the approaches proposed for addressing the SMC problem relies on the design of Garbled Circuit (GC). In Garbled Circuits (GCs), the function to be computed is represented as a Boolean circuit composed of binary gates. The input and output wire of each gate is masked such that the party evaluating the Garbled Boolean Circuits (GBC) cannot gain any information about the inputs or the intermediate results that appear during the function evaluation. The complexity of today's most efficient GC protocol depends linearly on the size of the Boolean circuit representation of the evaluated function. The total cost and run-time interaction between parties increase linearly with the number of gates and can be huge for complex GBCs. 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 XOR gates in a Boolean circuit have no cost for the secure computation protocol. Therefore, circuits with a reduced number of non-XOR gates are more convenient and one of the possible ways to reduce the complexity of the computation is to reduce the number of non-XOR gates in the Boolean circuit. Recalling that, the main aim of this work is to reduce the number of non-XOR gates, which directly results in a reduced number of interactions between the parties and transfer complexity at runtime, we present different approaches for reducing the communication cost of Secure Multi-party Computation (SMC) and improving the overall computation time and efficiency of the execution of SMC.
Abstract. We consider secure two-party computation in a multiple-execution setting, where two parties wish to securely evaluate the same circuit multiple times. We design efficient garbled-circuit-based two-party protocols secure against malicious adversaries. Recent works by Lindell (Crypto 2013) and Huang-Katz-Evans (Crypto 2013) have obtained op-timal complexity for cut-and-choose performed over garbled circuits in the single execution setting. We show that it is possible to obtain much lower amortized overhead for cut-and-choose in the multiple-execution setting. Our efficiency improvements result from a novel way to combine a recent technique of Lindell (Crypto 2013) with LEGO-based cut-and-choose techniques (TCC 2009, Eurocrypt 2013). In concrete terms, for 40-bit statistical security we obtain a 2 × improvement (per execution) in com-munication and computation for as few as 7 executions, and require only 8 garbled circuits (i.e., a 5 × improvement) per execution for as low as 3500 executions. Our results suggest the exciting possibility that secure two-party computation in the malicious setting can be less than an order of magnitude more expensive than in the semi-honest setting. 1
Secure multi-party computation (SMC) is an emerging topic which has been drawing growing attention during recent decades. There are many examples which show importance of SMC constructions in practice, such as privacy-preserving decision making and machine learning, auctions, private set intersection, and others. In this tutorial, we provide a comprehensive coverage of SMC techniques, starting from precise definitions and fundamental techniques. Consequently, a significant portion of the tutorial focuses on recent advances in general SMC constructions. We cover garbled circuit evaluation (GCE) and linear secret sharing (LSS) which are commonly used for secure two-party and multi-party computation, respectively. The coverage includes both standard adversarial models: semi-honest and malicious. For GCE, we start with the original Yao's garbled circuits construction [30] for semi-honest adversaries and consequently cover its recent optimizations such as the "free XOR,'' the garbled row reduction, the half-gates optimization, and the use of AES NI techniques. We follow with a discussion of techniques for making GCE resilient to malicious behavior, which includes the cut-and-choose approach and additional techniques to deter known attacks in the presence of malicious participants. In addition, we include the-state-of-the-art protocols for oblivious transfer (OT) and OT extension in the presence of semi-honest and malicious users. For LSS, we start from standard solutions for the semi-honest adversarial model including [5, 28] and consequently move to recent efficient constructions for semi-honest and malicious adversarial models. The coverage includes different types of corruption thresholds (with and without honest majority), which imply different guarantees with respect to abort.
Secure two-party computation enables two parties to evaluate a function cooperatively without revealing to either party anything beyond the function's output. The garbled-circuit technique, a generic approach to secure two-party computation for semi-honest participants, was developed by Yao in the 1980s, but has been viewed as being of limited practical significance due to its inefficiency. We demonstrate several techniques for improving the running time and memory requirements of the garbled-circuit technique, resulting in an implementation of generic secure two-party computation that is significantly faster than any previously reported while also scaling to arbitrarily large circuits. We validate our approach by demonstrating secure computation of circuits with over 109 gates at a rate of roughly 10 microseconds per garbled gate, and showing order-of-magnitude improvements over the best previous privacy-preserving protocols for computing Hamming distance, Levenshtein distance, Smith-Waterman genome alignment, and AES.
In this thesis we design and implement three approaches to provide efficient Secure Two- Party Computation (2PC) protocols that are secure in presence of malicious adversaries. The field of secure two-party computation enables two mutually distrusting parties, each with their own private input, to run a computation of an arbitrary program. At the end of the computation, nothing about their private input is leaked except for what can be learned from the output of the computation. The seminal work of Yao in 1986 provided the first proof that such a computation is feasible using the so called garbled circuits and given an Oblivious Transfer protocol. In this thesis, we follow Yao’s garbled circuit approach and focus on efficient protocols that are secure against malicious adversaries. We examine three different categories of optimization. In each category, we present a 2PC protocol, prove its security, and implement it as a proof of concept to demonstrate its running time in practice. Non-interactive Secure Computation: In this category, we offer the first implementation of a malicious 2PC protocol that reduces the required rounds of interaction between the two parties to only two rounds (i.e., each party sends only one message to the other party). Mixed Secure Two-Party Computation: In the second category we target big and complex programs and break them into subprograms. Then, we compute each subprogram using the most efficient 2PC protocol that is suitable for it. Finally, we securely connect these subprograms together. The goal is to reduce the overhead of the garbled circuits significantly, which results in a more efficient overall 2PC protocol for programs with specific properties. Secure Computation for Random Access Machine Programs: In the third category, we target programs that require random access to the memory (as opposed to a sequential access). We present the first efficient maliciously-secure protocol for computing such programs.