# The Hidden Communication Graph Model: Achieving Communication Locality and Optimal Resilience in the Presence of Adaptive Faults

## Nishanth Chandran and Wutichai Chongchitmate and Juan A. Garay and Shafi Goldwasser and Rafail Ostrovsky and Vassilis Zikas

```
```Secure multi-party 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 all the network participants over a complete network of point-to-point 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 communication locality, namely, the total number of point-to-point
channels that each party uses in the protocol, as a quality metric of MPC protocols. They
proved that assuming a public-key infrastructure (PKI) and a common reference string (CRS),
an MPC protocol can be constructed for computing any n-party function, with communication
locality O(logc n) and round complexity O(logc′ n), for appropriate constants c and c′. Their
protocol tolerates a static (i.e., non-adaptive) adversary corrupting up to t < ( 1 − ε)n parties 3
￼for any given constant 0 < ε < 1 . These results leave open the following questions: 3
￼(1) Can we achieve low communication locality and round complexity while tolerating adaptive adversaries?
(2) Can we achieve low communication locality with 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 symmetric-key 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 adaptive corruptions, under a standard
intractability assumption for adaptively secure protocols, namely, the existence of trapdoor
permutations whose domain has invertible sampling. This is done by using the SKI to derive
a sequence of random 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}