Rafail Ostrovsky - Publications

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 (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 In this work we answer both questions affirmatively. We consider the Boyle et al. model,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) (similarly to Boyle et al.) which tolerates up to t < n/2 adaptive corruptions, under a standard intractability assumption for adaptively secure protocols, namely, the existence of trapdoor permutation whose domain has invertible sampling. This is done by using the SKI to drive a sequence of random hidden communication graphs among players. A central new technique shows how to use these graphs to emulate a complete network in polylog (n) rounds while preserving polylog(n) locality. We also show how to remove the SKI setup assumption at the cost, however; of increasing the communication locality ( but not the round complexity) by a factor of √n.

comment: ITCS 2015 pp: 153-162

Fetch PDF file of the paper