Paper 2014/615
The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults
Nishanth Chandran, Wutichai Chongchitmate, Juan A. Garay, Shafi Goldwasser, Rafail Ostrovsky, and Vassilis Zikas
Abstract
Secure multiparty computation (MPC) has been thoroughly studied over the past decades. The vast majority of works assume a full communication pattern: every party exchanges messages with {\em all} the network participants over a complete network of pointtopoint channels. This can be problematic in modern large scale networks, where the number of parties can be of the order of millions, as for example when computing on large distributed data. Motivated by the above observation, Boyle, Goldwasser, and Tessaro [TCC 2013] recently put forward the notion of {\em communication locality}, namely, the total number of pointtopoint channels that each party uses in the protocol, as a quality metric of MPC protocols. They proved that assuming a publickey infrastructure (PKI) and a common reference string (CRS), an MPC protocol can be constructed for computing any $n$party function, with communication locality $\bigo[\log^c n]$ and round complexity $\bigo[\log^{c'} n]$, for appropriate constants $c$ and $c'$. Their protocol tolerates a static (i.e., nonadaptive) adversary corrupting up to $t<(\frac{1}{3}\epsilon)n$ parties for any given constant $0<\epsilon<\frac{1}{3}$. These results leave open the following questions: (1) Can we achieve low communication locality and round complexity while tolerating {\em adaptive} adversaries? \\ (2) Can we achieve low communication locality with {\em optimal resiliency} $t<n/2$? In this work we answer both questions affirmatively. First, we consider the model from [TCC 2013], where we replace the CRS with a symmetrickey infrastructure (SKI). In this model we give a protocol with communication locality and round complexity \polylog[n] (as in the [TCC~2013] work) which tolerates up to $t<n/2$ {\em adaptive} corruptions, under a standard intractability assumption for adaptively secure protocols, \vaddon{namely, the existence of enhanced trapdoor permutations and secure erasures.} This is done by using the SKI to derive a sequence of random {\it hidden communication graphs} among players. A central new technique then shows how to use these graphs to emulate a complete network in \polylog[n] rounds while preserving the \polylog[n] locality. Second, we show how we can even remove the SKI setup assumption at the cost, however, of increasing the communication locality (but not the round complexity) by a factor of~$\sqrt{n}$.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. MINOR revision.ITCS 2015
 Keywords
 secure multiparty computationcommunication localityadaptive security
 Contact author(s)
 vassilis zikas @ gmail com
 History
 20180706: last of 3 revisions
 20140813: received
 See all versions
 Short URL
 https://ia.cr/2014/615
 License

CC BY
BibTeX
@misc{cryptoeprint:2014/615, author = {Nishanth Chandran and Wutichai Chongchitmate and Juan A. Garay and Shafi Goldwasser and Rafail Ostrovsky and Vassilis Zikas}, title = {The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults}, howpublished = {Cryptology ePrint Archive, Paper 2014/615}, year = {2014}, note = {\url{https://eprint.iacr.org/2014/615}}, url = {https://eprint.iacr.org/2014/615} }