status: Published

Abstract Secure Two-Party Computation (2PC) protocols allow two parties to compute a function of their private inputs without revealing any information besides the output of the computation. There exist low cost general-purpose protocols for semi-honest parties that can be efficiently executed even on smartphones. However, for the case of malicious parties, current 2PC protocols are significantly less efficient, limiting their use to more resourceful devices. In this work we present an efficient 2PC protocol that is secure against malicious parties and is light enough to be used on mobile phones. The protocol is an adaptation of the protocol of Nielsen et al. (Crypto, 2012) to the Server-Aided setting, a natural relaxation of the plain model for secure computation that allows the parties to interact with a server (e.g., a cloud) who is assumed not to collude with any of the parties. Our protocol has two stages: In an offline stage - where no party knows which function is to be computed, nor who else is participating - each party interacts with the server and downloads a file. Later, in the online stage, when two parties decide to execute a 2PC together, they can use the files they have downloaded earlier to execute the computation with cost that is lower than the currently best semi-honest 2PC protocols. We show an implementation of our protocol for Android mobile phones, discuss several optimizations and report on its evaluation for various circuits. For example, the online stage for evaluating a single AES circuit requires only 2.5 seconds and can be further reduced to 1 second (amortized time) with multiple executions.

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 circuits 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.

Secure function evaluation (SFE) allows a set of mutually distrustful parties to evaluate a function of their joint inputs without revealing their inputs to each other. SFE has been the focus of active research and recent work suggests that it can be made practical. Unfortunately, current protocols and implementations have inherent limitations that are hard to overcome using standard and practical techniques. Among them are: (1) requiring participants to do work linear in the size of the circuit representation of the function; (2) requiring all parties to do the same amount of work; and (3) not being able to provide complete fairness.

The current move to Cloud Computing raises the need for verifiable delegation of computations, where a weak client delegates his computation to a powerful server, while maintaining the ability to verify that the result is correct. Although there are prior solutions to this problem, none of them is yet both general and practical for real-world use. We demonstrate a relatively efficient and general solution where the client delegates the computation to several servers, and is guaranteed to determine the correct answer as long as even a single server is honest. We show: A protocol for any efficiently computable function, with logarithmically many rounds, based on any collision-resistant hash family. The protocol is set in terms of Turing Machines but can be adapted to other computation models. An adaptation of the protocol for the X86 computation model and a prototype implementation, called Quin, for Windows executables. We describe the architecture of Quin and experiment with several parameters on live clouds. We show that the protocol is practical, can work with nowadays clouds, and is efficient both for the servers and for the client.