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.
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.
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) 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) 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.
Garbled Circuit (GC) is the main practical 2PC technique, yet despite great interest in its performance, GC notoriously resists improvement. Essentially, we only know how to evaluate GC functions gate-by-gate using encrypted truth tables; given input labels, the GC evaluator decrypts the corresponding output label. Interactive protocols enjoy more sophisticated techniques. For example, we can expose to a party a (masked) private value. The party can then perform useful local computation and feed the resulting cleartext value back into the MPC. Such techniques are not known to work for GC. We show that it is, in fact, possible to improve GC efficiency, while keeping its round complexity, by exposing masked private values to the evaluator. %without introducing rounds of communication. Our improvements use garbled one-hot encodings of values. By using this encoding we improve a number of interesting functions, e.g., matrix multiplication, integer multiplication, field element multiplication, field inverses and AES S-Boxes, integer exponents, and more. We systematize our approach by providing a framework for designing such GC modules. Our constructions are concretely efficient. E.g., we improve binary matrix multiplication inside GC by more than 6x in terms of communication and by more than 4x in terms of WAN wall-clock time. Our improvement circumvents an important GC lower bound and may open GC to further improvement.
Outsourced secure multiparty computation (SMC) protocols allow resource-constrained devices to execute input-private computation with great efficiency. Unfortunately, existing outsourced SMC protocols require that all parties know the function being evaluated, precluding applications where the function itself must remain private. We develop the first linear-complexity protocols for outsourcing private function evaluation (PFE), SMC protocols that provide input and function privacy. Assuming a semi-honest function holder, we build on existing two-party PFE constructions to develop outsourced protocols that are secure against a semi-honest, covert, or malicious outsourcing server and malicious mobile participants. To do this, we develop a garbling technique for combining public and private sub-circuits in a single computation. This allows us to apply auxiliary checks for malicious behaviour using only free-XOR gates. These protocols demonstrate the feasibility of outsourced PFE and provide a first step towards privacy-preserving applications for use in cloud computing.
Abstract. We consider generic Garbled Circuit (GC)-based techniques for Secure Function Evaluation (SFE) in the semi-honest model. We describe efficient GC constructions for addition, subtraction, multiplication, and comparison functions. Our circuits for subtraction and comparison are approximately two times smaller (in terms of garbled tables) than previous constructions. This implies corresponding computation and communication improvements in SFE of functions using our efficient building blocks. The techniques rely on recently proposed “free XOR ” GC technique. Further, we present concrete and detailed improved GC protocols for the problem of secure integer comparison, and related problems of auctions, minimum selection, and minimal distance. Performance improvement comes both from building on our efficient basic blocks and several problemspecific GC optimizations. We provide precise cost evaluation of our constructions, which serves as a baseline for future protocols.