Almost-Everywhere Secure Computation

Nishanth Chandran, Juan A. Garay, Rafail Ostrovsky

Nishanth Chandran, Pouyan Forghani, Juan A. Garay +3 more

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.

David Evans

Shailesh Vaya

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.

Juan A. Garay, Rafail Ostrovsky

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

Yuval Ishai