Communication Locality in Secure Multi-party Computation
We devise multi-party computation protocols for general secure function evaluation with the property that each party is only required to communicate with a small number of dynamically chosen parties. More explicitly, starting with n parties connected via a complete and synchronous network, our proto...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Book |
| Language: | English |
| Published: |
Springer Berlin Heidelberg
2019
|
| Online Access: | https://hdl.handle.net/1721.1/121532 |
| _version_ | 1826212969139142656 |
|---|---|
| author | Boyle, Elette Chantae Goldwasser, Shafrira Tessaro, Stefano |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Boyle, Elette Chantae Goldwasser, Shafrira Tessaro, Stefano |
| author_sort | Boyle, Elette Chantae |
| collection | MIT |
| description | We devise multi-party computation protocols for general secure function evaluation with the property that each party is only required to communicate with a small number of dynamically chosen parties. More explicitly, starting with n parties connected via a complete and synchronous network, our protocol requires each party to send messages to (and process messages from) at most polylog(n) other parties using polylog(n) rounds. It achieves secure computation of any polynomial-time computable randomized function f under cryptographic assumptions, and tolerates up to statically scheduled Byzantine faults. We then focus on the particularly interesting setting in which the function to be computed is a sublinear algorithm: An evaluation of f depends on the inputs of at most q = o(n) of the parties, where the identity of these parties can be chosen randomly and possibly adaptively. Typically, q = polylog(n). While the sublinear query complexity of f makes it possible in principle to dramatically reduce the communication complexity of our general protocol, the challenge is to achieve this while maintaining security: in particular, while keeping the identities of the selected inputs completely hidden. We solve this challenge, and we provide a protocol for securely computing such sublinear f that runs in polylog(n) + O(q) rounds, has each party communicating with at most q •polylog(n) other parties, and supports message sizes polylog(n) •(ℓ + n), where ℓ is the parties' input size. Our optimized protocols rely on a multi-signature scheme, fully homomorphic encryption (FHE), and simulation-sound adaptive NIZK arguments. However, we remark that multi-signatures and FHE are used to obtain our bounds on message size and round complexity. Assuming only standard digital signatures and public-key encryption, one can still obtain the property that each party only communicates with polylog(n) other parties. We emphasize that the scheduling of faults can depend on the initial PKI setup of digital signatures and the NIZK parameters. © 2013 International Association for Cryptologic Research. Keywords: Homomorphic Encryption, Honest Party, Swap Gate, Secure Multiparty Computation, Secure Function Evaluation |
| first_indexed | 2024-09-23T15:41:02Z |
| format | Book |
| id | mit-1721.1/121532 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:41:02Z |
| publishDate | 2019 |
| publisher | Springer Berlin Heidelberg |
| record_format | dspace |
| spelling | mit-1721.1/1215322022-09-29T15:29:51Z Communication Locality in Secure Multi-party Computation Boyle, Elette Chantae Goldwasser, Shafrira Tessaro, Stefano Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Massachusetts Institute of Technology. Department of Mathematics Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science We devise multi-party computation protocols for general secure function evaluation with the property that each party is only required to communicate with a small number of dynamically chosen parties. More explicitly, starting with n parties connected via a complete and synchronous network, our protocol requires each party to send messages to (and process messages from) at most polylog(n) other parties using polylog(n) rounds. It achieves secure computation of any polynomial-time computable randomized function f under cryptographic assumptions, and tolerates up to statically scheduled Byzantine faults. We then focus on the particularly interesting setting in which the function to be computed is a sublinear algorithm: An evaluation of f depends on the inputs of at most q = o(n) of the parties, where the identity of these parties can be chosen randomly and possibly adaptively. Typically, q = polylog(n). While the sublinear query complexity of f makes it possible in principle to dramatically reduce the communication complexity of our general protocol, the challenge is to achieve this while maintaining security: in particular, while keeping the identities of the selected inputs completely hidden. We solve this challenge, and we provide a protocol for securely computing such sublinear f that runs in polylog(n) + O(q) rounds, has each party communicating with at most q •polylog(n) other parties, and supports message sizes polylog(n) •(ℓ + n), where ℓ is the parties' input size. Our optimized protocols rely on a multi-signature scheme, fully homomorphic encryption (FHE), and simulation-sound adaptive NIZK arguments. However, we remark that multi-signatures and FHE are used to obtain our bounds on message size and round complexity. Assuming only standard digital signatures and public-key encryption, one can still obtain the property that each party only communicates with polylog(n) other parties. We emphasize that the scheduling of faults can depend on the initial PKI setup of digital signatures and the NIZK parameters. © 2013 International Association for Cryptologic Research. Keywords: Homomorphic Encryption, Honest Party, Swap Gate, Secure Multiparty Computation, Secure Function Evaluation 2019-07-09T14:11:14Z 2019-07-09T14:11:14Z 2013 2019-05-29T14:59:44Z Book http://purl.org/eprint/type/ConferencePaper 9783642365935 9783642365942 0302-9743 1611-3349 https://hdl.handle.net/1721.1/121532 Boyle, Elette, et al. “Communication Locality in Secure Multi-Party Computation.” Theory of Cryptography, edited by Amit Sahai, vol. 7785, Springer Berlin Heidelberg (2013): 356–76. en 10.1007/978-3-642-36594-2_21 Theory of Cryptography Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer Berlin Heidelberg other univ website |
| spellingShingle | Boyle, Elette Chantae Goldwasser, Shafrira Tessaro, Stefano Communication Locality in Secure Multi-party Computation |
| title | Communication Locality in Secure Multi-party Computation |
| title_full | Communication Locality in Secure Multi-party Computation |
| title_fullStr | Communication Locality in Secure Multi-party Computation |
| title_full_unstemmed | Communication Locality in Secure Multi-party Computation |
| title_short | Communication Locality in Secure Multi-party Computation |
| title_sort | communication locality in secure multi party computation |
| url | https://hdl.handle.net/1721.1/121532 |
| work_keys_str_mv | AT boyleelettechantae communicationlocalityinsecuremultipartycomputation AT goldwassershafrira communicationlocalityinsecuremultipartycomputation AT tessarostefano communicationlocalityinsecuremultipartycomputation |