**
The HiddenGraph Model: Communication Locality and Optimal Resiliency with Adaptive Faults
**

*
Nishanth Chandran,
wutichai Chongchitmate,
Juan A. Garay,
Shafi Goldwasser,
Rafail Ostrovsky,
Vassilis Zikas
*
**
**

**
Abstract:
**

The vast majority of works on secure multi-party computation (MPC) 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 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(log^{ c } n)
and round complexity O(log^{c'} n), for appropriate constants c and c^{∈}. Their protocol tolerates a static (i.e., non-adaptive) adversary corrupting up to t<(1/3-w)n
parties for any given constant o* adaptive* adversaries?

(2) Can we achieve low communication locality with optimal resiliency t

**comment:**
ITCS 2015 pp: 153-162

Fetch PDF file of the paper

Back to Publications List |