We present the design and implementation of a compiler that automatically generates protocols that perform two-party computations. The input to our protocol is the specification of a computation with secret inputs (e.g., a signature algorithm) expressed using operations in the field Zq of integers modulo a prime q and in the multiplicative subgroup of order q in Z*p for q|p-1 with generator g. The output of our compiler is an implementation of each party in a two-party protocol to perform the same computation securely, i.e., so that both parties can together compute the function but neither can alone. The protocols generated by our compiler are provably secure, in that their strength can be reduced to that of the original cryptographic computation via simulation arguments. Our compiler can be applied to various cryptographic primitives (e.g., signature schemes, encryption schemes, oblivious transfer protocols) and other protocols that employ a trusted party (e.g., key retrieval, key distribution).
We present the design and implementation of a compiler that automatically generates protocols that perform two-party computations. The input to our protocol is the specification of a computation with secret inputs (e.g., a signature algorithm) expressed using operations in the field Zq of integers modulo a prime q and in the multiplicative subgroup of order q in Z*p for q|p-1 with generator g. The output of our compiler is an implementation of each party in a two-party protocol to perform the same computation securely, i.e., so that both parties can together compute the function but neither can alone. The protocols generated by our compiler are provably secure, in that their strength can be reduced to that of the original cryptographic computation via simulation arguments. Our compiler can be applied to various cryptographic primitives (e.g., signature schemes, encryption schemes, oblivious transfer protocols) and other protocols that employ a trusted party (e.g., key retrieval, key distribution).
We present the design and implementation of a compiler that automatically generates protocols that perform two-party computations. The input to our protocol is the specification of a computation with secret inputs (e.g., a signature algorithm) expressed using operations in the field Zq of integers modulo a prime q and in the multiplicative subgroup of order q in Z*p for q|p-1 with generator g. The output of our compiler is an implementation of each party in a two-party protocol to perform the same computation securely, i.e., so that both parties can together compute the function but neither can alone. The protocols generated by our compiler are provably secure, in that their strength can be reduced to that of the original cryptographic computation via simulation arguments. Our compiler can be applied to various cryptographic primitives (e.g., signature schemes, encryption schemes, oblivious transfer protocols) and other protocols that employ a trusted party (e.g., key retrieval, key distribution).
We present the design and implementation of a compiler that automatically generates protocols that perform two-party computations. The input to our protocol is the specification of a computation with secret inputs (e.g., a signature algorithm) expressed using operations in the field Zq of integers modulo a prime q and in the multiplicative subgroup of order q in Z # p for q|p 1 with generator g. The output of our compiler is an implementation of each party in a two-party protocol to perform the same computation securely, i.e., so that both parties can together compute the function but neither can alone. The protocols generated by our compiler are provably secure, in that their strength can be reduced to that of the original cryptographic computation via simulation arguments. Our compiler can be applied to various cryptographic primitives (e.g., signature schemes, encryption schemes, oblivious transfer protocols) and other protocols that employ a trusted party (e.g., key retrieval, key distribution).
We study the problem of secure two-party computation of arithmetic circuits in the presence of active ("malicious") parties. This problem is motivated by privacy-preserving numerical computations, such as ones arising in the context of machine learning training and classification, as well as in threshold cryptographic schemes. In this work, we design, optimize, and implement anactively secure protocol for secure two-party arithmetic computation. A distinctive feature of our protocol is that it can make a fully modular black-box use of any passively secure implementation of oblivious linear function evaluation (OLE). OLE is a commonly used primitive for secure arithmetic computation, analogously to the role of oblivious transfer in secure computation for Boolean circuits. For typical (large but not-too-narrow) circuits, our protocol requires roughly 4 invocations of passively secure OLE per multiplication gate. This significantly improves over the recent TinyOLE protocol (Döttling et al., ACM CCS 2017), which requires 22 invocations of actively secure OLE in general, or 44 invocations of a specific code-based passively secure OLE. Our protocol follows the high level approach of the IPS compiler (Ishai et al., CRYPTO 2008, TCC 2009), optimizing it in several ways. In particular, we adapt optimization ideas that were used in the context of the practical zero-knowledge argument system Ligero (Ames et al., ACM CCS 2017) to the more general setting of secure computation, and explore the possibility of boosting efficiency by employing a "leaky" passively secure OLE protocol. The latter is motivated by recent (passively secure) lattice-based OLE implementations in which allowing such leakage enables better efficiency. We showcase the performance of our protocol by applying its implementation to several useful instances of secure arithmetic computation. On "wide" circuits, such as ones computing a fixed function on many different inputs, our protocol is 5x faster and transmits 4x less data than the state-of-the-art Overdrive (Keller et al., Eurocrypt 2018). Our benchmarks include a general passive-to-active OLE compiler, authenticated generation of "Beaver triples", and a system for securely outsourcing neural network classification. The latter is the first actively secure implementation of its kind, strengthening the passive security provided by recent related works (Mohassel and Zhang, IEEE S&P 2017; Juvekar et al., USENIX 2018).
Consider several parties that do not trust each other, yet they wish to correctly compute some common function of their local inputs while keeping these inputs private. This problem is known as "Secure Multi-Party Computation", and was introduced by Andrew Yao in 1982. Secure multi-party computations have some real world examples like electronic auctions, electronic voting or fingerprinting. In this thesis we consider the case where there are only two parties involved. This is known as "Secure Two-Party Computation". If there is a trusted third party called Carol, then the problem is pretty straightforward. The participating parties could hand their inputs in Carol who can compute the common function correctly and could return the outputs to the corresponding parties. The goal is to achieve (almost) the same result when there is no trusted third party. Cryptographic protocols are designed in order to solve these kinds of problems. These protocols are analyzed within an appropriate model in which the behavior of parties is structured. The basic level is called the Semi-Honest Model where parties are assumed to follow the protocol specification, but later can derive additional information based on the messages which have been received so far. A more realistic model is the so-called Malicious Model. The common approach is to first analyze a protocol in the semi-honest model and then later extend it into the malicious model. Any cryptographic protocol for secure two-party computation must satisfy the following security requirements: correctness, privacy and fairness. It must guarantee the correctness of the result while preserving the privacy of the parties’ inputs, even if one of the parties is malicious and behaves arbitrarily throughout the protocol. It must also guarantee fairness. This roughly means that whenever a party aborts the protocol prematurely, he or she should not have any advantage over the other party in discovering the output. The main question for researchers is to construct new protocols that achieve the above mentioned goals for secure multi-party computation. Of course, such protocols must be secure in a given model, as well as be as efficient as possible. In 1986, Yao presented the first general protocol for secure two-party computation which was applicable only to the semi-honest model. He uses a tool called "Garbled Circuit". Yao’s protocol uses the underlying primitives ("Pseudorandom Generator" and "Oblivious Transfer") as blackboxes which lead to efficient results. After Yao’s work many variants and improvements have been proposed for the malicious model. In this thesis, we design several new protocols for secure two-party computation based on Yao’s garbled circuit. Before we present the details of our new designs, we first show several weaknesses, security flaws or problems with the existing protocols in the literature. We first work in the semi-honest model and then extend it into the malicious model by presenting new protocols. Finally we add fairness to our protocol. Oblivious transfer (OT) is a fundamental primitive in modern cryptography which is useful for implementing protocols for secure multi-party computation. We study several variants of oblivious transfer in this thesis. We present a new protocol for the so-called "Committed OT". This protocol is very efficient in the sense that it is quite good in comparison to the most efficient committed OT protocols in the literature. The abovementioned flaw with the use of OT can be fixed with our committed oblivious transfer protocol. Furthermore, it is more general than all previous protocols, and, therefore, it is of independent interest. We also deal with fairness in this thesis. For protocols based on garbled circuit, so far only Benny Pinkas has presented a protocol in the literature for achieving fairness. We show a subtle problem with this protocol where the privacy of the inputs of one party can be compromised. We also describe this problem in detail which is in fact related to the fairness, and finally propose a more efficient scheme that does achieve fairness.
The design of secure protocols that implement arbitrarily desired functionalities is a major part of modern cryptography. Taking the opposite perspective, the design of any cryptographic scheme may be viewed as the design of a secure protocol for implementing a suitable functionality. Still, we believe that it makes sense to differentiate between basic cryptographic primitives (which involve little interaction) like encryption and signature schemes, on the one hand, and general cryptographic protocols, on the other hand. In this chapter we consider general results concerning secure multi –party computations, where the two –party case is an important special case. In a nutshell, these results assert that one can construct protocols for securely computing any desirable multi–party functionality (see the following terminology). Indeed, what is striking about these results is their generality, and we believe that the wonder is not diminished by the (various alternative) conditions under which these results hold. Our focus on the general study of secure multi–party computation (rather than on protocols for solving specific problems) is natural in the context of the theoretical treatment of the subject matter. We wish to highlight the importance of this general study to practice. Firstly, this study clarifies fundamental issues regarding security in a multi–party environment. Secondly, it draws the lines between what is possible in principle and what is not. Thirdly, it develops general techniques for designing secure protocols. And last, sometimes it may even yield schemes (or modules) that may be incorporated in practical systems.