We consider a recently proposed model for secure computation appropriate to the setting of low degree networks called almost everywhere secure computation. This model of multiparty computation allows a few honest parties to not achieve the canonical guarantees of Correctness and Privacy. Such honest parties may not be able to communicate reliably or securely with other honest parties in the network due to lack of infrastructure. We explain why a straightforward hybrid argument employed in the previous work can be used to realize privacy only when honest-but-curious type passive corruptions are considered. We further note that the notion of almost everywhere secure computation is theoretically challenging and practically relevant only when malicious corruptions are allowed. We argue and emphasize why simulation based reduction approach taken by the author is the only way to meaningfully realize privacy of almost everywhere secure computation. We present such an approach and show how to realize a.e.s.c. for general Byzantine corruptions, resolving the principle open problem in this line of research. Finally, we note several technical and conceptual improvements to the results given in previous work.
We consider a recently proposed model for secure computation appropriate to the setting of low degree networks called almost everywhere secure computation. This model of multiparty computation allows a few honest parties to not achieve the canonical guarantees of Correctness and Privacy. Such honest parties may not be able to communicate reliably or securely with other honest parties in the network due to lack of infrastructure. We explain why a straightforward hybrid argument employed in the previous work can be used to realize privacy only when honest-but-curious type passive corruptions are considered. We further note that the notion of almost everywhere secure computation is theoretically challenging and practically relevant only when malicious corruptions are allowed. We argue and emphasize why simulation based reduction approach taken by the author is the only way to meaningfully realize privacy of almost everywhere secure computation. We present such an approach and show how to realize a.e.s.c. for general Byzantine corruptions, resolving the principle open problem in this line of research. Finally, we note several technical and conceptual improvements to the results given in previous work.
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.
Secure multi-party computation (MPC) is a central problem in cryptography. Unfortunately, it is well known that MPC is possible if and only if the underlying communication network has very large connectivity—specifically, (t), wheretis the number of potential corruptions in the network. This impossibility result renders existing MPC results far less applicable in practice, since most deployed networks have in fact a very small degree. In this paper, we show how to circumvent this impossibility result and achieve meaningful security guarantees for graphs with small degree (such as expander graphs and several other topologies). In fact, the notion we introduce, which we call almost-everywhere MPC, building on the notion of almost-everywhere agreement due to Dwork, Peleg, Pippenger and Upfal, allows the degree of the network to be much smaller than the total number of allowed corruptions. In essence, our definition allows the adversary to implicitly wiretap some of the good nodes by corrupting sufficiently many nodes in the “neighborhood ” of those nodes. We show protocols that satisfy our new definition, retaining both correctness and privacy for most nodes despite small connectivity, no matter how the adversary chooses his corruptions. Instrumental in our constructions is a new model and protocol for the secure message transmission (SMT) problem, which we call SMT by public discussion, and which we use for the establishment of pairwise secure channels in limited connectivity networks. Key words: Secure multi-party computation, almost-everywhere agreement, secure message transmission, expander graphs, bounded-degree networks. 1
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.
Most existing work on secure multi-party computation (MPC) ignores a key idiosyncrasy of modern communication networks, that there are a limited number of communication paths between any two nodes, many of which might even be corrupted. The problem becomes particularly acute in the information-theoretic setting, where the lack of trusted setups (and the cryptographic primitives they enable) makes communication over sparse networks more challenging. The work by Garay and Ostrovsky [EUROCRYPT’08] on almost-everywhere MPC (AE-MPC), introduced “best-possible security” properties for MPC over such incomplete networks, where necessarily some of the honest parties may be excluded from the computation. In this work, we provide a universally composable definition of almost-everywhere security , which allows us to automatically and accurately capture the guarantees of AE-MPC (as well as AE-communication, the analogous “best-possible security” version of secure communication) in the Universal Composability (UC) framework of Canetti. Our results offer the first simulation-based treatment of this important but under-investigated problem, along with the first simulation-based proof of AE-MPC. To achieve that goal, we state and prove a general composition theorem, which makes precise the level or “quality” of AE-security that is obtained when a protocol’s hybrids are replaced with almost-everywhere components.
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.
Most of this book has considered two-party and multiparty computation with security with (unfair) abort. This security notion allows the adversary to force the honest parties to abort even depending on the outputs of corrupted parties. (Note, however, that the adversary is not allowed to bias the output of honest parties in any other manner.) This relaxation of security is necessary if one wishes to tolerate arbitrarily many corruptions. A further relaxation considers computational security, where the adversary is assumed to be computationally bounded, e.g., probabilistic polynomial time. In this setting, any circuit can be securely realized even when arbitrarily many parties are corrupted, as long as one is willing to sacrifice fairness and robustness.