The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults
Copyright © 2015 ACM. 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, w...
| Main Authors: | , , , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Association for Computing Machinery (ACM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137551 |
| _version_ | 1826202436050616320 |
|---|---|
| author | Chandran, Nishanth Chongchitmate, Wutichai Garay, Juan A. Goldwasser, Shafi Ostrovsky, Rafail Zikas, Vassilis |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Chandran, Nishanth Chongchitmate, Wutichai Garay, Juan A. Goldwasser, Shafi Ostrovsky, Rafail Zikas, Vassilis |
| author_sort | Chandran, Nishanth |
| collection | MIT |
| description | Copyright © 2015 ACM. 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 pointto- 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/3 - ε)n parties for any given constant 0 < ε < 1/3. These results leave open the following questions: (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. 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 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 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. |
| first_indexed | 2024-09-23T12:07:26Z |
| format | Article |
| id | mit-1721.1/137551 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T12:07:26Z |
| publishDate | 2021 |
| publisher | Association for Computing Machinery (ACM) |
| record_format | dspace |
| spelling | mit-1721.1/1375512023-04-13T14:44:29Z The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults Chandran, Nishanth Chongchitmate, Wutichai Garay, Juan A. Goldwasser, Shafi Ostrovsky, Rafail Zikas, Vassilis Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Copyright © 2015 ACM. 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 pointto- 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/3 - ε)n parties for any given constant 0 < ε < 1/3. These results leave open the following questions: (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. 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 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 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. 2021-11-05T17:27:30Z 2021-11-05T17:27:30Z 2015-01 2019-05-29T15:48:09Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137551 Chandran, Nishanth, Chongchitmate, Wutichai, Garay, Juan A., Goldwasser, Shafi, Ostrovsky, Rafail et al. 2015. "The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults." en 10.1145/2688073.2688102 Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Association for Computing Machinery (ACM) other univ website |
| spellingShingle | Chandran, Nishanth Chongchitmate, Wutichai Garay, Juan A. Goldwasser, Shafi Ostrovsky, Rafail Zikas, Vassilis The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults |
| title | The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults |
| title_full | The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults |
| title_fullStr | The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults |
| title_full_unstemmed | The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults |
| title_short | The Hidden Graph Model: Communication Locality and Optimal Resiliency with Adaptive Faults |
| title_sort | hidden graph model communication locality and optimal resiliency with adaptive faults |
| url | https://hdl.handle.net/1721.1/137551 |
| work_keys_str_mv | AT chandrannishanth thehiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT chongchitmatewutichai thehiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT garayjuana thehiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT goldwassershafi thehiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT ostrovskyrafail thehiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT zikasvassilis thehiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT chandrannishanth hiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT chongchitmatewutichai hiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT garayjuana hiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT goldwassershafi hiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT ostrovskyrafail hiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults AT zikasvassilis hiddengraphmodelcommunicationlocalityandoptimalresiliencywithadaptivefaults |