This doctoral dissertation presents contributions advancing the state-of-the-art of secure two-party computation (S2PC) — a cryptographic primitive that allows two mutually distrustful parties, with respective private inputs, to evaluate a function of their combined input, while ensuring privacy of inputs and outputs and integrity of the computation, externally indistinguishable from an interaction mediated by a trusted party. The dissertation shows that S2PC can be made more practical by means of innovative cryptographic techniques, namely by engineered use of commitment schemes with special properties, enabling more efficient protocols, with provable security and applicable to make systems more dependable. This is one further step toward establishing S2PC as a practical tool for privacy-preserving applications. The main technical contribution is a new protocol for S2PC of Boolean circuits, based on an innovative technique called forge-and-lose.1 Building on top of a traditional cut-and-choose of garbled circuits (cryptographic versions of Boolean circuits), the protocol improves efficiency by reducing by a factor of approximately 3 the needed number of garbled circuits. This significantly reduces a major communication component of S2PC with malicious parties, for circuits of practical size. The protocol achieves simulatable S2PC-with-commitments, producing random commitments of the circuit input and output bits of both parties. The commitments also enable direct linkage of several S2PCs in a malicious adversarial setting. As second result, the dissertation describes an improvement to the efficiency of one of the needed sub-protocols: simulatable two-party coin-flipping.1 The sub-protocol is based on a new universally composable commitment scheme that for bit-strings of increasing size can achieve an asymptotic communication-complexity rate arbitrarily close to 1. The dissertation then discusses how S2PC-with-commitments can enable in brokered identification systems a difficult-to-achieve privacy property — a kind of unlinkability.1 This mitigates a vector of potential mass surveillance by an online central entity (a hub), which is otherwise empowered in systems being developed at nation scale for authentication of citizens. When the hub mediates between identity providers and service providers the authentication of users, an adequate S2PC (e.g., of a block-cipher) can prevent the hub from learning user pseudonyms that would allow linking transactions of the same user across different services providers. 1 Parts of these contributions were previously presented at ASIACRYPT 2013, PETS 2015 and PKC 2016.
This doctoral dissertation presents contributions advancing the state-of-the-art of secure two-party computation (S2PC) — a cryptographic primitive that allows two mutually distrustful parties, with respective private inputs, to evaluate a function of their combined input, while ensuring privacy of inputs and outputs and integrity of the computation, externally indistinguishable from an interaction mediated by a trusted party. The dissertation shows that S2PC can be made more practical by means of innovative cryptographic techniques, namely by engineered use of commitment schemes with special properties, enabling more efficient protocols, with provable security and applicable to make systems more dependable. This is one further step toward establishing S2PC as a practical tool for privacy-preserving applications. The main technical contribution is a new protocol for S2PC of Boolean circuits, based on an innovative technique called forge-and-lose.1 Building on top of a traditional cut-and-choose of garbled circuits (cryptographic versions of Boolean circuits), the protocol improves efficiency by reducing by a factor of approximately 3 the needed number of garbled circuits. This significantly reduces a major communication component of S2PC with malicious parties, for circuits of practical size. The protocol achieves simulatable S2PC-with-commitments, producing random commitments of the circuit input and output bits of both parties. The commitments also enable direct linkage of several S2PCs in a malicious adversarial setting. As second result, the dissertation describes an improvement to the efficiency of one of the needed sub-protocols: simulatable two-party coin-flipping.1 The sub-protocol is based on a new universally composable commitment scheme that for bit-strings of increasing size can achieve an asymptotic communication-complexity rate arbitrarily close to 1. The dissertation then discusses how S2PC-with-commitments can enable in brokered identification systems a difficult-to-achieve privacy property — a kind of unlinkability.1 This mitigates a vector of potential mass surveillance by an online central entity (a hub), which is otherwise empowered in systems being developed at nation scale for authentication of citizens. When the hub mediates between identity providers and service providers the authentication of users, an adequate S2PC (e.g., of a block-cipher) can prevent the hub from learning user pseudonyms that would allow linking transactions of the same user across different services providers. 1 Parts of these contributions were previously presented at ASIACRYPT 2013, PETS 2015 and PKC 2016.
Abstract We present a new protocol for maliciously secure two-party computation based on cut-and-choose of garbled circuits using the recent idea of “forge-and-loose”, which eliminates around a factor 3 of garbled circuits that needs to be constructed and evaluated. Our protocol introduces a new way to realize the “forge-and-loose” approach, which avoids an auxiliary secure two-party computation protocol, does not rely on any number theoretic assumptions and parallelizes well in a same instruction, multiple data (SIMD) framework. With this approach we prove our protocol universally composable-secure against a malicious adversary assuming access to oblivious transfer, commitment and coin-tossing functionalities in the random oracle model. Finally, we construct, and benchmark, a SIMD implementation of this protocol using a GPU as a massive SIMD device. The findings compare favorably with all previous implementations of maliciously secure, two-party com-putation. 1
This paper reports on a number of conceptual and technical contributions to the currently very lively field of two-party computation (2PC) based on garbled circuits. Our main contributions are as follows: 1. We propose the notion of an interactive garbling scheme, where the garbled circuit is generated through an interactive protocol between the garbler and the evaluator. The garbled circuit is correct and privacy preserving even if one of the two parties was acting maliciously during garbling. The security notion is game based. 2. We show that an interactive garbling scheme combined with a Universally Composable (UC) secure oblivious transfer protocol can be used in a black-box manner to implement two-party computation (2PC) UC securely against any probabilistic polynomial time static and malicious adversary. The protocol abstracts many recent protocols for implementing 2PC from garbled circuits and will allow future designers of interactive garbling schemes to prove security with the simple game based definitions, as opposed to directly proving UC security for each new scheme. 3. We propose an instantiation of interactive garbling by designing a new protocol in the LEGO family of protocols for efficient garbling against a malicious adversary. The new protocol is based on several new technical contributions and optimizations, for example making it possible to get distinct output to both parties with minimal overhead. The scheme makes black-box usage of a XOR-homomorphic commitment scheme, an authentic, private and oblivious garbling scheme and a 2-correlation-robust and collision-resistant hash function. When comparing our resulting 2PC protocol to previous works in the same setting we see a noticeable reduction in the communication that directly depends on the size of the circuit (e.g. 33% for circuits larger than 501,271 AND gates).
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.
Applying cut-and-choose techniques to Yao’s garbled circuit protocol has been a promising approach for designing efficient Two-Party Computation (2PC) with malicious and covert security, as is evident from various optimizations and software implementations in the recent years. We revisit the security and efficiency properties of this popular approach and propose alternative constructions and definitions that are more suitable for use in practice. • We design an efficient fully-secure malicious 2PC protocol for two-output functions that only requires O(t|C|) symmetric-key operations (with small constant factors) where |C | is the circuit size and t is a statistical security parameter. This is essentially the optimal complexity for protocols based on cut-and-choose, resolving a main question left open by the previous work on the subject. Our protocol utilizes novel techniques for enforcing garbler’s input consistency and handling twooutput functions that are more efficient than all prior solutions. • Motivated by the goal of eliminating the all-or-nothing nature of 2PC with covert security (that privacy and correctness are fully compromised if the adversary is not caught in the challenge phase), we propose a new security definition for 2PC that strengthens the guarantees provided by the standard
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.
Secure Multi-Party Computation (MPC) protocols allow a group of mutually distrusting users to compute a function jointly on their inputs without revealing any information beyond the output. For many years, implementations of MPC protocols have targeted security against semi-honest adversaries, i.e., attackers are assumed to execute the protocol honestly but try to learn private information after the fact. Protocols secure against stronger and more realistic malicious adversaries, who could behave arbitrarily during the protocol execution, were known to exist but were much less efficient. This thesis introduces a new paradigm to construct extremely efficient MPC protocols with malicious security. In particular, this thesis consists of three major contributions. 1. We introduce the authenticated garbling framework, and present an efficient concrete instantiation of the protocol. The resulting protocol partially closes the gap between semi-honest and malicious MPC protocols asymptotically; the implementation of the protocol represents the state-of-the-art system for malicious two-party computation. 2. We discuss how to apply authenticated garbling to the multi-party setting, where all-but-one parties can be corrupted by the adversary. The resulting protocol improves upon the best previous constant-round protocol by orders of magnitude. We also present a system that, for the first time, enables MPC executions among hundreds of parties, distributed globally. 3. We present a series of optimizations to two-party authenticated garbling by interpreting authenticated garbling in a new way. The improved malicious protocol has essentially the same concrete efficiency as the best semi-honest protocol in the preprocessing model. 4. We develop these protocols in EMP-toolkit, a practical and efficient MPC tool that can be used to build new protocols and to develop applications using our existing protocols.