Blazing Fast 2PC in the Offline/Online Setting with Security for Malicious Adversaries.

Yehuda Lindell, Ben Riva

Published Jan 1, 2015• 5 citations

Abstract

Recently, several new techniques were presented to dramatically improve key parts of secure two-party computation (2PC) protocols that use the cut-and-choose paradigm on garbled cir-cuits for 2PC with security against malicious adversaries. These include techniques for reducing the number of garbled circuits (Lindell 13, Huang et al. 13, Lindell and Riva 14, Huang et al. 14) and techniques for reducing the overheads besides garbled circuits (Mohassel and Riva 13, Shen and Shelat 13). We design a highly optimized protocol in the offline/online setting that makes use of all state-of-the-art techniques, along with several new techniques that we introduce. A crucial part of our protocol is a new technique for enforcing consistency of the inputs used by the party who garbles the circuits. This technique has both theoretical and practical advantages over previous methods. We present a prototype implementation of our new protocol, which is also the first imple-mentation of the amortized cut-and-choose technique of Lindell and Riva (Crypto 2014). Our prototype achieves a speed of just 7 ms in the online stage and just 74 ms in the offline stage per 2PC invoked, for securely computing AES in the presence of malicious adversaries (using 9 threads on two 2.9GHz machines located in the same Amazon region). We note that no prior work has gone below one second overall on average for the secure computation of AES for mali-cious adversaries (nor below 20ms in the online stage). Our implementation securely evaluates SHA-256 (which is a much bigger circuit) with 33 ms online time and 206 ms offline time, per 2PC invoked. 1

Related papers

Blazing Fast 2PC in the Offline/Online Setting with Security for Malicious Adversaries

Yehuda Lindell, Ben Riva

ACM SIGSAC Conference on Computer and Communications Security (CCS)Oct 6, 201565 citations

Faster Malicious 2-Party Secure Computation with Online/Offline Dual Execution

Peter Rindal, Mike Rosulek

We describe a highly optimized protocol for generalpurpose secure two-party computation (2PC) in the presence of malicious adversaries. Our starting point is a protocol of Kolesnikov et al. (TCC 2015). We adapt that protocol to the online/offline setting, where two parties repeatedly evaluate the same function (on possibly different inputs each time) and perform as much of the computation as possible in an offline preprocessing phase before their inputs are known. Along the way we develop several significant simplifications and optimizations to the protocol. We have implemented a prototype of our protocol and report on its performance. When two parties on Amazon servers in the same region use our implementation to securely evaluate the AES circuit 1024 times, the amortized cost per evaluation is 5.1ms offline + 1.3ms online. The total offline+online cost of our protocol is in fact less than the online cost of any reported protocol with malicious security. For comparison, our protocol’s closest competitor (Lindell & Riva, CCS 2015) uses 74ms offline + 7ms online in an identical setup. Our protocol can be further tuned to trade performance for leakage. As an example, the performance in the above scenario improves to 2.4ms offline + 1.0ms online if we allow an adversary to learn a single bit about the honest party’s input with probability 2−20 (but not violate any other security property, e.g. correctness).

USENIX Security SymposiumJan 1, 201640 citations

Amortizing Garbled Circuits

Yan Huang, Jonathan I. Katz, Vladimir Kolesnikov +2 more

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

Lecture notes in computer scienceAug 17, 20142 citations

Cut-and-Choose Based Two-Party Computation in the Online/Offline and Batch Settings.

Yehuda Lindell, Ben Riva

Protocols for secure two-party computation enable a pair of mistrusting parties to compute a joint function of their private inputs without revealing anything but the output. One of the fundamental techniques for obtaining secure computation is that of Yao’s garbled circuits. In the setting of malicious adversaries, where the corrupted party can follow any arbitrary (polynomial-time) strategy in an attempt to breach security, the cut-and-choose technique is used to ensure that the garbled circuit is constructed correctly. The cost of this technique is the construction and transmission of multiple circuits; specifically, s garbled circuits are used in order to obtain a maximum cheating probability of 2−s. In this paper, we show how to reduce the amortized cost of cut-and-choose based secure two-party computation to O s logN garbled circuits when N secure computations are run. We use this method to construct a secure protocol in the batch setting. Next, we show how the cut-

Jan 1, 20140 citations

Garbled Circuits Checking Garbled Circuits: More Efficient and Secure Two-Party Computation.

Payman Mohassel, Ben Riva

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

Jan 1, 20130 citations

Design and Implementation of Maliciously Secure Two-Party Computation Based on Garbled Circuits

Afshar, Arash

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.

Jan 1, 20170 citations