Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Lecture notes in computer science

Communication Locality in Secure Multi-party Computation: How to Run Sublinear Algorithms in a Distributed Setting

Elette Boyle, Shafi Goldwasser, Stefano Tessaro

Published Jan 1, 2013• 63 citations
Publisher
DOI
10.1007/978-3-642-36594-2_21

Related papers

Lean and Fast Secure Multi-party Computation: Minimizing Communication and Local Computation using a Helper

Johannes Schneider

International Joint Conference on e-Business and Telecommunications (ICETE)•Jan 1, 2016•6 citations

Secure Multi-Party Computation: Theory, practice and applications

Chuan Zhao, Shengnan Zhao, Minghao Zhao +4 more

Information Sciences•Oct 16, 2018•538 citations

The Price of Low Communication in Secure Multi-party Computation

Juan A. Garay, Yuval Ishai, Rafail Ostrovsky +1 more

Traditional protocols for secure multi-party computation among n parties communicate at least a linear (in n) number of bits, even when computing very simple functions. In this work we investigate the feasibility of protocols with sublinear communication complexity. Concretely, we consider two clients, one of which may be corrupted, who wish to perform some “small” joint computation using n servers but without any trusted setup. We show that enforcing sublinear communication complexity drastically affects the feasibility bounds on the number of corrupted parties that can be tolerated in the setting of information-theoretic security. We provide a complete investigation of security in the presence of semi-honest adversaries—static and adaptive, with and without erasures—and initiate the study of security in the presence of malicious adversaries. For semi-honest static adversaries, our bounds essentially match the corresponding bounds when there is no communication restriction—i.e., we can tolerate up to $$t < (1/2 -\epsilon )n$$ corrupted parties. For the adaptive case, however, the situation is different. We prove that without erasures even a small constant fraction of corruptions is intolerable, and—more surprisingly—when erasures are allowed, we prove that $$t < (1 - \sqrt{0.5} - \epsilon )n$$ corruptions can be tolerated, which we also show to be essentially optimal. The latter optimality proof hinges on a new treatment of probabilistic adversary structures that may be of independent interest. In the case of active corruptions in the sublinear communication setting, we prove that static “security with abort” is feasible when $$t < (1/2 - \epsilon )n$$ , namely, the bound that is tight for semi-honest security. All of our negative results in fact rule out protocols with sublinear message complexity.

Lecture notes in computer science•Jan 1, 2017•25 citations

Cloud-SMPC: two-round multilinear maps secure multiparty computation based on LWE assumption

Yun Luo, Yuling Chen, Tao Li +2 more

Abstract Cloud computing has data leakage from all parties, security protection of private data, and existing solutions do not provide a trade-off between security and overhead. With distributed data communication due to data barriers, information interaction security and data computation security have become challenges for secure computing. Combining cloud computing with secure multiparty computation can provide a higher level of data protection while maintaining the benefits of cloud computing. In this case, data can be stored in the cloud and computed through SMPC protocols, thus protecting the privacy and security of the data. However, multiple rounds of information interaction are often required, increasing the communication overhead, and the security strength is limited by the hardness assumption. In this paper, we work to achieve an optimal setting of the number of rounds in secure multi-party computation on the cloud to achieve a sublinear communication overhead and improve the security concept. A 2-round SMPC protocol is constructed in the framework of Universally Composable (UC). A 2-round SMPC protocol is constructed that uses multilinear maps based on the Learning from Errors (LWE) assumption. The participant encodes the input and sends it via broadcast to reduce the interaction, homomorphic computational encoding information for secure access to computational data and secure the SMPC protocol through UC security. This paper extends the participants to multiple parties, reduces the communication rounds to 2, the protocol achieves sublinear communication overhead in poly polynomial time, smaller setup size to poly(k), and static security is achieved.

Journal of Cloud Computing Advances Systems and Applications•Jan 22, 2024•13 citations

Secure multi-party computation problems and their applications

Wenliang Kevin Du, Mikhail J. Atallah

New Security Paradigms Workshop•Jan 1, 2001•19 citations

Secure multi-party computation in large networks

Varsha Dani, Valerie King, Mahnush Movahedi +2 more

Distributed Computing•Sep 26, 2016•20 citations
Traditional protocols for secure multi-party computation among n parties communicate at least a linear (in n) number of bits, even when computing very simple functions. In this work we investigate the feasibility of protocols with sublinear communication complexity. Concretely, we consider two clients, one of which may be corrupted, who wish to perform some “small” joint computation using n servers but without any trusted setup. We show that enforcing sublinear communication complexity drastically affects the feasibility bounds on the number of corrupted parties that can be tolerated in the setting of information-theoretic security. We provide a complete investigation of security in the presence of semi-honest adversaries—static and adaptive, with and without erasures—and initiate the study of security in the presence of malicious adversaries. For semi-honest static adversaries, our bounds essentially match the corresponding bounds when there is no communication restriction—i.e., we can tolerate up to t<(1/2−ϵ)nt < (1/2 -\epsilon )nt<(1/2−ϵ)n corrupted parties. For the adaptive case, however, the situation is different. We prove that without erasures even a small constant fraction of corruptions is intolerable, and—more surprisingly—when erasures are allowed, we prove that t<(1−0.5−ϵ)nt < (1 - \sqrt{0.5} - \epsilon )nt<(1−0.5​−ϵ)n corruptions can be tolerated, which we also show to be essentially optimal. The latter optimality proof hinges on a new treatment of probabilistic adversary structures that may be of independent interest. In the case of active corruptions in the sublinear communication setting, we prove that static “security with abort” is feasible when t<(1/2−ϵ)nt < (1/2 - \epsilon )nt<(1/2−ϵ)n , namely, the bound that is tight for semi-honest security. All of our negative results in fact rule out protocols with sublinear message complexity.
Abstract Cloud computing has data leakage from all parties, security protection of private data, and existing solutions do not provide a trade-off between security and overhead. With distributed data communication due to data barriers, information interaction security and data computation security have become challenges for secure computing. Combining cloud computing with secure multiparty computation can provide a higher level of data protection while maintaining the benefits of cloud computing. In this case, data can be stored in the cloud and computed through SMPC protocols, thus protecting the privacy and security of the data. However, multiple rounds of information interaction are often required, increasing the communication overhead, and the security strength is limited by the hardness assumption. In this paper, we work to achieve an optimal setting of the number of rounds in secure multi-party computation on the cloud to achieve a sublinear communication overhead and improve the security concept. A 2-round SMPC protocol is constructed in the framework of Universally Composable (UC). A 2-round SMPC protocol is constructed that uses multilinear maps based on the Learning from Errors (LWE) assumption. The participant encodes the input and sends it via broadcast to reduce the interaction, homomorphic computational encoding information for secure access to computational data and secure the SMPC protocol through UC security. This paper extends the participants to multiple parties, reduces the communication rounds to 2, the protocol achieves sublinear communication overhead in poly polynomial time, smaller setup size to poly(k), and static security is achieved.