Paper 2019/156
Efficient Constructions for Almosteverywhere Secure Computation
Siddhartha Jayanti, Srinivasan Raghuraman, and Nikhil Vyas
Abstract
The importance of efficient MPC in today's world needs no retelling. An obvious barebones requirement to execute protocols for MPC is the ability of parties to communicate with each other. Traditionally, we solve this problem by assuming that every pair of parties in the network share a dedicated secure link that enables reliable message transmission. This assumption is clearly impractical as the number of nodes in the network grows, as it has today. In their seminal work, Dwork, Peleg, Pippenger and Upfal introduced the notion of almosteverywhere secure primitives in an effort to model the reality of large scale global networks and study the impact of limited connectivity on the properties of fundamental faulttolerant distributed tasks. In this model, the underlying communication network is sparse and hence some nodes may not even be in a position to participate in the protocol (all their neighbors may be corrupt, for instance). A protocol for almost everywhere reliable message transmission, which would guarantee that a large subset of the network can transmit messages to each other reliably, implies a protocol for almosteverywhere agreement where nodes are required to agree on a value despite malicious or byzantine behavior of some subset of nodes, and an almosteverywhere agreement protocol implies a protocol almosteverywhere secure MPC that is unconditionally or informationtheoretically secure. The parameters of interest are the degree $d$ of the network, the number $t$ of corrupted nodes that can be tolerated and the number $x$ of nodes that the protocol may give up. Prior work achieves $d = O(1)$ for $t = O(n/\log n)$ and $d = O(\log^{q}n)$ for $t = O(n)$ for some fixed constant $q > 1$. In this work, we first derive message protocols which are efficient with respect to the total number of computations done across the network. We use this result to show an abundance of networks with $d = O(1)$ that are resilient to $t = O(n)$ random corruptions. This randomized result helps us build networks which are resistant to worstcase adversaries. In particular, we improve the state of the art in the almost everywhere reliable message transmission problem in the worstcase adversary model by showing the existence of an abundance of networks that satisfy $d = O(\log n)$ for $t = O(n)$, thus making progress on this question after nearly a decade. Finally, we define a new adversarial model of corruptions that is suitable for networks shared amongst a large group of corporations that: (1) do not trust each other, and (2) may collude, and construct optimal networks achieving $d = O(1)$ for $t = O(n)$ in this model.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint. Minor revision.
 Keywords
 MPCalmosteverywherebyzantine faulttolerance
 Contact author(s)

jayanti @ mit edu
srirag @ mit edu
nikhilv @ mit edu  History
 20190220: received
 Short URL
 https://ia.cr/2019/156
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/156, author = {Siddhartha Jayanti and Srinivasan Raghuraman and Nikhil Vyas}, title = {Efficient Constructions for Almosteverywhere Secure Computation}, howpublished = {Cryptology ePrint Archive, Paper 2019/156}, year = {2019}, note = {\url{https://eprint.iacr.org/2019/156}}, url = {https://eprint.iacr.org/2019/156} }