Abstract. Secure computation enables mutually suspicious parties to compute a joint function of their private inputs while providing strong security guarantees. However, its use in practice seems limited. We argue that one of the reasons for this is that the model of computation on the web is not suited to the type of communication patterns needed for secure computation. Specifically, in most web scenarios clients independently connect to servers, interact with them and then leave. This rules out the use of secure computation protocols that require that all participants interact simultaneously. We initiate a study of secure computation in a client-server model where each client connects to the server once and interacts with it, without any other client necessarily being connected at the same time. We point out some inherent limitations in this model and present definitions that capture what can be done. We also present a general feasibility result and several truly practical protocols for a number of functions of interest. All our protocols are based on standard assumptions, and we achieve security both in the semi-honest and malicious adversary models. 1
Abstract. Secure computation enables mutually suspicious parties to compute a joint function of their private inputs while providing strong security guarantees. However, its use in practice seems limited. We argue that one of the reasons for this is that the model of computation on the web is not suited to the type of communication patterns needed for secure computation. Specifically, in most web scenarios clients independently connect to servers, interact with them and then leave. This rules out the use of secure computation protocols that require that all participants interact simultaneously. We initiate a study of secure computation in a client-server model where each client connects to the server once and interacts with it, without any other client necessarily being connected at the same time. We point out some inherent limitations in this model and present definitions that capture what can be done. We also present a general feasibility result and several truly practical protocols for a number of functions of interest. All our protocols are based on standard assumptions, and we achieve security both in the semi-honest and malicious adversary models. 1
The notion of secure computation is central to cryptography. Introduced in the seminal works of Yao [FOCS'82, FOCS'86] and Goldreich, Micali and Wigderson [STOC'87], secure multiparty computation allows a group of (mutually) distrustful parties to jointly compute any functionality over their individual private inputs in such a manner that the honest parties obtain the correct outputs and no group of malicious parties learn anything beyond their inputs and the prescribed outputs. General feasibility results for secure computation were given by Yao [FOCS'86] and Goldreich et al. [STOC'87] more than two decades ago. Subsequent to these works, designing secure computation protocols that can tolerate more powerful adversaries and satisfy stronger notions of security has been a very active area of research. In this dissertation, we study two such new frontiers in the area of secure computation.
In the first part of this dissertation, we initiate a study of designing leakage-resilient interactive protocols. Specifically, we consider the scenario where an adversary, in addition to corrupting a subset of parties, can leak (potentially via physical attacks) arbitrary information from the secret state of any honest party. This is in contrast to the standard notion of secure computation where it is assumed that the adversary only has black-box'' access to the honest parties. In particular, we formalize a meaningful definition of leakage-resilient zero knowledge proof systems and provide constructions that satisfy our notion. We also discuss various applications of our results.
The second part of this dissertation concerns with the general question of whether it is possible to securely run cryptographic protocols over an insecure network environment such as the Internet. It is well-known that the standard notion of secure computation is only relevant to the stand-alone setting where a single protocol is being executed in isolation; as such it does not guarantee security when multiple protocol sessions may be executed concurrently under the control of an adversary who is present across all sessions. We consider the open problem of constructing secure password-based authenticated key exchange protocols in such a setting in the plain model (i.e., without assuming any trusted infrastructure or random oracles). We give the first construction of such a protocol based on standard cryptographic assumptions. Our results are in fact much more general, and extend to other functionalities w.r.t. a (necessarily) weakened notion of concurrently secure computation.
The results presented in this dissertation stem from two papers which are joint works with Sanjam Garg and Amit Sahai, and with Vipul Goyal and Rafail Ostrovsky, respectively.
Choi et al. (TCC 2013) introduced the notion of multi-client verifiable computation (MVC) in which a set of clients outsource to an untrusted server the computation of a function f over their collective inputs in a sequence of time periods. In that work, the authors defined and realized multi-client verifiable computation satisfying soundness against a malicious server and privacy against the semi-honest corruption of a single client. Very recently, Goldwasser et al. (Eurocrypt 2014) provided an alternative solution relying on multi-input functional encryption. Here we conduct a systematic study of MVC, with the goal of satisfying stronger security requirements. We begin by introducing a simulation-based notion of security that provides a unified way of defining soundness and privacy, and automatically captures several attacks not addressed in previous work. We then explore the feasibility of achieving this notion of security. Assuming no collusion between the server and the clients, we demonstrate a protocol for multi-client verifiable computation that achieves strong security in several respects. When server-client collusion is possible, we show (somewhat surprisingly) that simulation-based security cannot be achieved in general, even assuming semi-honest behavior.
We consider secure two-party computation in the client-server model. In our scenario, two adversaries operate separately but simultaneously, each of them corrupting one of the parties and a restricted subset of servers that they interact with. We model security in this setting via the local universal composability framework introduced by Canetti and Vald and show that informationtheoretically secure two-party computation is possible if and only if there is always at least one server which remains uncorrupted. Moreover, in our protocols each of the servers only needs to communicate with the two clients, i.e. no messages are exchanged directly between servers. This communication pattern is minimal.
Abstract. In the setting of secure multiparty computation, a set of parties wish to jointly compute some function of their inputs. Such a computation must preserve certain security properties, like privacy and correctness, even if some of the participating parties or an external adversary collude to attack the honest parties. Until this paper, all protocols for general secure computation assumed that the parties can communicate reliably via authenticated channels. In this paper, we consider the feasibility of secure computation without any setup assumption. We consider a completely unauthenticated setting, where all messages sent by the parties may be tampered with and modified by the adversary (without the honest parties being able to detect this fact). In this model, it is not possible to achieve the same level of security as in the authenticated-channel setting. Nevertheless, we show that meaningful security guarantees can be provided. In particular, we define a relaxed notion of what it means to “securely compute ” a function in the unauthenticated setting. Then, we construct protocols for securely realizing any functionality in the stand-alone model, with no setup assumptions whatsoever. In addition, we construct universally composable protocols for securely realizing any functionality in the common reference string model (while still in an unauthenticated network). We also show that our protocols can be used to provide conceptually simple and unified solutions to a number of problems that were studied separately in the past, including password-based authenticated key exchange and non-malleable commitments. 1
The goal of secure two-party computation is to enable two parties to cooperatively evaluate a function that takes private data from both parties as input without exposing any of the private data. At the end of the computation, the participants learn nothing more than the output of the function. The two-party secure computation systems have three properties: (1) the application involves inputs from two independent parties; (2) each party wants to keep its own data secret; and (3) the participants agree to reveal the output of the computation. That is, the result itself does not imply too much information about either party's private input. Informally, the security requirements are that nothing is learned from the protocol other than the output (privacy), and that the output is distributed according to the prescribed functionality (correctness). The threat models in the two-party computation assume the presence of three different types of adversaries: 1) Semi honest, 2) Malicious and 3) Covert.
We initiate the study of secure multi-party computation (MPC) in a server-aided setting, where the parties have access to a single server that (1) does not have any input to the computation; (2) does not receive any output from the computation; but (3) has a vast (but bounded) amount of computational resources. In this setting, we are concerned with designing protocols that minimize the computation of the parties at the expense of the server. We develop new definitions of security for this server-aided setting that generalize the standard simulation-based definitions for MPC and allow us to formally capture the existence of dishonest but non-colluding participants. This requires us to introduce a formal characterization of non-colluding adversaries that may be of independent interest. We then design general and special-purpose server-aided MPC protocols that are more efficient (in terms of computation and communication) for the parties than the alternative of running a standard MPC protocol (i.e., without the server). Our main general-purpose protocol provides security when there is at least one honest party with input. We also construct a new and efficient server-aided protocol for private set intersection and give a general transformation from any secure delegated computation scheme to a server-aided two-party protocol. ∗Microsoft Research. senyk@microsoft.com. †University of Calgary. pmohassel@cspc.ucalgary.ca. Work done while visiting Microsoft Research. ‡Columbia University. mariana@cs.columbia.edu. Work done as an intern at Microsoft Research.