In secure multi-party computation $n$ parties jointly evaluate an $n$-variate function $f$ in the presence of an adversary which can corrupt up till $t$ parties. Almost all the works that have appeared in the literature so far assume the presence of authenticated channels between the parties. This assumption is far from realistic. Two directions of research have been borne from relaxing this (strong) assumption: (a) The adversary is virtually omnipotent and can control all the communication channels in the network, (b) Only a partially connected topology of authenticated channels is guaranteed and adversary controls a subset of the communication channels in the network. This work introduces a new setting for (unconditional) secure multiparty computation problem which is an interesting intermediate model with respect to the above well studied models from the literature (by sharing a salient feature from both the above models). We consider the problem of (unconditional) secure multi-party computation when 'some' of the communication channels connecting the parties can be corrupted passively as well as actively. For this setting, some honest parties may be connected to several other honest parties via corrupted channels and may not be able to authentically communicate with them. Such parties may not be assured the canonical guarantees of correctness or privacy. We present refined definitions of security for this new intermediate model of unconditional multiparty computation. We show how to adapt protocols for (Unconditional) secure multiparty computation to realize the definitions and also argue the tightness of the results achieved by us.
In secure multi-party computation n parties jointly evaluate an n-variate function f in the presence of an adversary which can corrupt up till t parties. Almost all the works that have appeared in the literature so far assume the presence of authenticated channels between the parties. This assumption is far from realistic. Two directions of research have been borne from relaxing this (strong) assumption: (a) The adversary is virtually omnipotent and can control all the communication channels in the network, (b) Only a partially connected topology of authenticated channels is guaranteed and adversary controls a subset of the communication channels in the network. This work introduces a new setting for (unconditional) secure multiparty computation problem which is an interesting intermediate model with respect to the above well studied models from the literature (by sharing a salient feature from both the above models). We consider the problem of (unconditional) secure multi-party computation when 'some' of the communication channels connecting the parties can be corrupted passively as well as actively. For this setting, some honest parties may be connected to several other honest parties via corrupted channels and may not be able to authentically communicate with them. Such parties may not be assured the canonical guarantees of correctness or privacy. We present refined definitions of security for this new intermediate model of unconditional multiparty computation. We show how to adapt protocols for (Unconditional) secure multiparty computation to realize the definitions and also argue the tightness of the results achieved by us.
Secure multiparty computation of a multivariate function is a central problem in cryptography. It is well known that secure multiparty computation can be realized by a set of n parties iff the connectivity of the underlying (authenticated) communication network is more than twice the number of corrupted parties. This impossibility result makes secure multiparty computation far less applicable in practice, as most deployed networks have a degree much lower than O(n) and one would ideally like to be able to tolerate Θ(n) corrupted parties. In this work we consider a recently proposed model for (Unconditional) secure multiparty computation for networks of low degrees for which authenticated channels are available only between very few pairs of parties. Not all honest parties may be expected to achieve traditional security guarantees of multiparty computation for this model because of theoretical limitations posed by lack of infrastructure. Honest parties which are not given canonical guarantees of Correctness and Privacy are called ”sacrificed” and the resulting notion is called almost everywhere secure computation. In this conceptual note, we investigate the previous results about this model by Garay and Ostrovsky'2008. We explain why these results hold only for weak honest-but-curious type passive corruptions. We emphasize why the results for almost everywhere secure computation are theoretically interesting and practically relevant only when active malicious corruptions are allowed. We argue the limitation of hybrid argument for realizing privacy property when Byzantine corruptions are allowed. From this we deduce that simulation based reduction approach is necessary to realize even input indistinguishability type definition of privacy for the stand alone setting. We present a conceptual exposition of the simulator based approach for defining privacy of a.e.s.c. Finally, we present a brief overview of technicalities involved in realizing a.e.s.c. when malicious corruptions are allowed.
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
. This paper improves on the classical results in unconditionally secure multi-party computation among a set of n players, by considering a model with three simultaneously occurring types of player corruption: the adversary can actively corrupt (i.e. take full control over) up to ta players and, additionally, can passively corrupt (i.e. read the entire information of) up to tp players and fail-corrupt (i.e. stop the computation of) up to tf other players. The classical results in multi-party computation are for the special cases of only passive (ta = tf = 0) or only active (tp = tf = 0) corruption. In the passive case, every function can be computed securely if and only if tp ! n=2. In the active case, every function can be computed securely if and only if ta ! n=3; when a broadcast channel is available, then this bound is ta ! n=2. These bounds are tight. Strictly improving these results, one of our results states that, in addition to tolerating ta ! n=3 actively corrupted players, pr...
This paper improves on the classical results in uncondition- ally secure multi-party computation among a set of n players, by consid- ering a model with three simultaneously occurring types of player cor- ruption: the adversary can actively corrupt (i.e. take full control over) up to ta players and, additionally, can passively corrupt (i.e. read the entire information of) up to tp players and fail-corrupt (i.e. stop the compu- tation of) up to tf other players. The classical results in multi-party computation are for the special cases of only passive (ta = tf =0 ) or only active (tp = tf = 0) corruption. In the passive case, every function can be computed securely if and only if tp <n = 2. In the active case, every function can be computed securely if and only if ta <n =3; when a broadcast channel is available, then this bound is ta <n =2. These bounds are tight. Strictly improving these results, one of our results states that, in addi- tion to tolerating ta <n =3 actively corrupted players, privacy can be guaranteed against every minority, thus tolerating additional tp n=6 passively corrupted players. These protocols require no broadcast and have an exponentially small failure probability. We further show that the bound t<n =2 for passive corruption holds even if the adversary is additionally allowed to make the passively corrupted players fail. Moreover, we characterize completely the achievable thresholds ta, tp and tf for four scenarios. Zero failure probability is achievable if and only if 3ta +2 tp + tf <n ; this holds whether or not a broadcast chan- nel is available. Exponentially small failure probability with a broadcast channel is achievable if and only if 2ta +2 tp +tf <n ; without broadcast, the additional condition 3ta + tf <n is necessary and sucient. In this corrected version, an error pointed out by Damg ard (Dam99) is corrected.
Abstract. Existing communication models for multiparty computation (MPC) either assume that all messages are delivered eventually or any message can be lost. Under the former assumption, MPC protocols guaranteeing output delivery are known. However, this assumption may not hold in some network settings like the Internet where messages can be lost due to denial of service attack or heavy network congestion. On the other hand, the latter assumption may be too conservative. Known MPC protocols developed under this assumption have an undesirable feature: output delivery is not guaranteed even only one party suffers message loss. In this work, we propose a communication model which makes an intermediate assumption on message delivery. In our model, there is a common global clock and three types of parties: (i) Corrupted parties (ii) Honest parties with connection problems (where message delivery is never guaranteed) (iii) Honest parties that can normally communicate but may lose a small fraction of messages at each round due to transient network problems. We define secure MPC under this model. Output delivery is guaranteed to type (ii) parties that do not abort and type (iii) parties. Let n be the total number of parties, ef and ec be upper bounds on the number of corrupted parties and type (ii) parties respectively. We construct a secure MPC protocol for n> 4ef + 3ec. Protocols for broadcast and verifiable secret sharing are constructed along the way. 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.