In classical secure multi-party computation (SMPC) it is assumed that a fixed and a priori known set of parties wants to securely evaluate a function of their private inputs. This assumption implies that online problems, in which the set of parties that arrive and leave over time are not a priori known, are not covered by the classical setting. Therefore, the notion of online SMPC has been introduced, and a general feasibility result has been proven that shows that any online algorithm can be implemented as a distributed protocol that is secure in this setting [22, 23]. However, so far, no online SMPC protocol that implements a concrete online algorithm has been proposed and evaluated such that the practicality of the constructive proof is an open question.
In classical secure multi-party computation (SMPC) it is assumed that a fixed and a priori known set of parties wants to securely evaluate a function of their private inputs. This assumption implies that online problems, in which the set of parties that arrive and leave over time are not a priori known, are not covered by the classical setting. Therefore, the notion of online SMPC has been introduced, and a general feasibility result has been proven that shows that any online algorithm can be implemented as a distributed protocol that is secure in this setting [22, 23]. However, so far, no online SMPC protocol that implements a concrete online algorithm has been proposed and evaluated such that the practicality of the constructive proof is an open question.
To date, ideal functionalities securely realized with secure multi-party computation (SMPC) mainly considers functions of the private input of a fixed number of a priori known parties. In this paper, we generalize these definitions such that protocols implementing online algorithms in a distributed fashion can be proven to be privacy-preserving. Online algorithms compute online functionalities that allow parties to join and leave over time, to provide multiple inputs and to obtain multiple outputs. In particular, the set of parties participating changes over time, i. e., at different points in time different sets of parties evaluate a function over their private inputs. To this end, we propose the notion of an online trusted third party that allows to prove the security of SMPC protocols implementing online functionalities or online algorithms, respectively. We show that any online functionality can be implemented perfectly secure in the presence of a semi-honest adversary, if strictly less than 1/2 of the parties participating are corrupted. We show that the same result holds in the presence of a malicious adversary if it corrupts strictly less than 1/3 of the parties and always allows the corrupted parties to arrive.
In secure multi-party computation (SMPC), it is considered that multiple parties that are known to each other evaluate a function over their private inputs in a secure fashion. The participating parties do not learn anything about each other's private inputs beyond what can be deduced from their own input and output. The assumption that the parties know each other, however, does not seem suitable for all potential applications of SMPC. In some applications participants may not only want to hide their private inputs and outputs, but may also want to hide the fact that they are participating in a given function evaluation in the first place. We therefore propose an anonymous system for SMPC that allows parties to anonymously evaluate a function of their private inputs in a fully distributed and secure fashion. The proposed system allows authorized parties to execute an SMPC protocol robust with penalty against a dishonest majority in the presence of a malicious adversary. During the protocol execution, the system guarantees that all participating parties stay anonymous w. r. t. each other as well as any third parties. In addition, it guarantees that in each function evaluation all participating parties are unique, i. e., no party can participate as more than one entity.
In this paper, comparative study of different available Secure Multiparty Computation (SMC) protocols have been addressed. In SMC, a set of parties wishes to jointly compute some function on their inputs. This computation must preserve certain security properties, like privacy and correctness. The general approach for such kind of computation is to make use of trusted third party to do the computation and then announce the result publicly. The major problem with this approach is that it is difficult to find a third party which is trusted by all the parties providing the inputs. This implies that the data of parties must be secured. Security is meant to achieve correctness of the result of computation and keeping the party’s input private even if some of the parties are corrupted.
In 1982, Yao presented a protocol that allowed two parties to compute over their private inputs while revealing nothing but the final output. This first theoretical construction originated a fruitful line of research exploring the possibilities of the cryptographic technique known as multi-party computation, or MPC. Today, we have MPC schemes with practical efficiency that can be used for a wide range of applications and use cases, from securing cryptographic keys to training Machine Learning models on private data. Despite the advancements from the past few decades, we have only started to bridge the gap between theory and practice, and several obstacles stand in the way of the widespread adoption of MPC. First, the performance overhead depends heavily on the computation we want to perform. Not all computations are well-suited to be distributed with MPC, and algorithms must usually be refactored before they can be executed securely. Furthermore, the practical efficiency of most modern protocols quickly deteriorates as the number of parties increases and comes at the expense of the security guarantees provided. On the other hand, almost all academic works assume a static set of MPC parties, all pairwise connected by dedicated channels in a network without delays or failures. Yet, these assumptions are hardly achievable in current real-world networks. In this thesis, we study three practical aspects of multi-party computation: (i) we discuss how to improve performance by designing algorithms tailor-made for execution with MPC. To this end, we present and evaluate secure auction mechanisms for the financial setting and for the peer-to-peer electricity market. (ii) We analyse the information leakage from the MPC computation outputs. In particular, we focus on the case of individual and private correlated outputs, for which we propose a new privacy notion. Lastly, (iii) we consider the problem of building efficient large-scale MPC. We explore the possibilities and limitations associated with standard (fully connected) networks and present a new protocol with a star-like network topology and resilience against delayed parties.
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.
We introduce and study the notion of non-interactive secure multiparty computation (NIMPC). An NIMPC protocol for a function f(x1,..., xn) is specified by a joint probability distribution R = (R1,..., Rn) and local encoding functions Enci(xi, Ri), 1 ≤ i ≤ n. Given correlated randomness (R1,..., Rn) ∈R R, each party Pi, using its input xi and its randomness Ri, computes the message mi = Enci(xi, Ri). The messagesm1,...,mn can be used to decode f(x1,..., xn). For a set T ⊆ [n], the protocol is said to be T-robust if revealing the messages (Enci(xi, Ri))i 6∈T together with the random-ness (Ri)i∈T gives the same information about (xi)i 6∈T as an oracle access to the function f restricted to these input values. Namely, a coalition T can learn no more than the restriction of f fixing the inputs of uncorrupted parties, which, in this non-interactive setting, one cannot hope to hide. For 0 ≤ t ≤ n, the protocol is t-robust if it is T-robust for every T of size at most t and it is fully robust if it is n-robust. A 0-robust NIMPC protocol for f coincides with a protocol in the private simultaneous messages model of Feige et al. (STOC 1994). In the setting of computational (indistinguishability-based) security, fully robust NIMPC is implied by multi-input functional encryption, a notion that was recently introduced by Goldwasser et al. (Euro-