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

Leibniz international proceedings in informatics

MPC with Low Bottleneck-Complexity: Information-Theoretic Security and More

Hannah Keller, Claudio Orlandi, Anat Paskin-Cherniavsky, Divya Ravi

Published Jan 1, 2023• 2 citations
Publisher

Abstract

The bottleneck-complexity (BC) of secure multiparty computation (MPC) protocols is a measure of the maximum number of bits which are sent and received by any party in protocol. As the name suggests, the goal of studying BC-efficient protocols is to increase overall efficiency by making sure that the workload in the protocol is somehow "amortized" by the protocol participants. Orlandi et al. [Orlandi et al., 2022] initiated the study of BC-efficient protocols from simple assumptions in the correlated randomness model and for semi-honest adversaries. In this work, we extend the study of [Orlandi et al., 2022] in two primary directions: (a) to a larger and more general class of functions and (b) to the information-theoretic setting. In particular, we offer semi-honest secure protocols for the useful function classes of abelian programs, "read-k" non-abelian programs, and "read-k" generalized formulas. Our constructions use a novel abstraction, called incremental function secret-sharing (IFSS), that can be instantiated with unconditional security or from one-way functions (with different efficiency trade-offs).

DOI
10.4230/lipics.itc.2023.11

Related papers

The Bottleneck Complexity of Secure Multiparty Computation

Elette Boyle, Abhishek Jain, Manoj Prabhakaran +1 more

In this work, we initiate the study of bottleneck complexity as a new communication efficiency measure for secure multiparty computation (MPC). Roughly, the bottleneck complexity of an MPC protocol is defined as the maximum communication complexity required by any party within the protocol execution. We observe that even without security, bottleneck communication complexity is an interesting measure of communication complexity for (distributed) functions and propose it as a fundamental area to explore. While achieving O(n) bottleneck complexity (where n is the number of parties) is straightforward, we show that: (1) achieving sublinear bottleneck complexity is not always possible, even when no security is required. (2) On the other hand, several useful classes of functions do have o(n) bottleneck complexity, when no security is required. Our main positive result is a compiler that transforms any (possibly insecure) efficient protocol with fixed communication-pattern for computing any functionality into a secure MPC protocol while preserving the bottleneck complexity of the underlying protocol (up to security parameter overhead). Given our compiler, an efficient protocol for any function f with sublinear bottleneck complexity can be transformed into an MPC protocol for f with the same bottleneck complexity. Along the way, we build cryptographic primitives - incremental fully-homomorphic encryption, succinct non-interactive arguments of knowledge with ID-based simulation-extractability property and verifiable protocol execution - that may be of independent interest.

Leibniz international proceedings in informatics•Jan 1, 2018•11 citations

Measures of efficiency for secure multiparty computation

Rafail Ostrovsky, Clint Givens

Multiparty computation (MPC) is a powerful and generic cryptographic framework capable of realizing essentially any cryptographic task (functionality) while preserving privacy and robustness. In the MPC model, a group of mutually distrustful parties seek to jointly compute a function f of their privately held inputs x1, ..., xn, while revealing no information about those inputs beyond what is entailed by the function output(s). Some portion of these players may be corrupted, controlled by a centralized adversary who directs their (mis)behavior and seeks to gain information on private inputs or to disrupt the protocol execution. In this work, we examine the resource requirements of information-theoretically secure multiparty computation. In particular, we look at trade-offs involving what we call assumptions, by which we mean two aspects of the model's setup: (1) the extent to which parties are connected by secure, pairwise communication channels; and (2) the usage (as a black box) of a channel—a primitive which enforces consistency among views by allowing a single party to send a message to all other parties which is guaranteed to be consistent, even if the broadcaster is corrupted. Part I of this work focuses on the first network-model assumption, that of the graph's connectivity by pairwise channels. We show upper and lower bounds on communication complexity in the Secure Message Transmission with Public Discussion (SMT-PD) model, as a function of the threshold of corrupted parties. The SMT-PD model, which abstracts the problem of secure communication over a partially connected network, includes two components: a public and a set of simple channels. We show significant improvements in both areas: on the channel, we reduce communication to logarithmic in terms of the message's bit-length m, where the previous best result was linear in m; on the simple channels, we reduce from O(mn) to O(mn/(n−t)), where n is the number of simple channels and t is a bound on the number of corrupted channels. Using tools from information theory, we show this amount of simple-wire communication is essentially optimal. Finally, we give an amortized solution which drastically improves communication over channel when the protocol is repeated many times sequentially. Part II shifts focus to the second network-model assumption, the use of an atomic broadcast primitive. Here we show that three broadcast rounds suffice for general secure computation, while two broadcast rounds are necessary. In particular we show that even for the natural and important functionality of Weak Secret Sharing—a type of distributed commitment—there is no protocol which uses only a single broadcast and achieves better than an explicit constant probability of success (so the protocol's success cannot be a function of a security parameter).

•Jan 1, 2013•0 citations

Lower Bounds on the Bottleneck Complexity of Secure Multiparty Computation

Reo Eriguchi, Keitaro Hiwatashi

Secure multiparty computation (MPC) is a cryptographic primitive which enables multiple parties to jointly compute a function without revealing any extra information on their private inputs. Bottleneck complexity is an efficiency measure that captures the load-balancing aspect of MPC protocols, defined as the maximum amount of communication required by any party. In this work, we study the problem of establishing lower bounds on the bottleneck complexity of MPC protocols. While the previously known techniques for lower bounding total communication complexity can also be applied to bottleneck complexity, they do not provide nontrivial bounds in the correlated randomness model, which is commonly assumed by existing protocols achieving low bottleneck complexity, or they are applied only to functions of limited practical interest. We propose several novel techniques for lower bounding the bottleneck complexity of MPC protocols. Our methods derive nontrivial lower bounds even in the correlated randomness model and apply to practically relevant functions including the sum function and threshold functions. Furthermore, our lower bounds demonstrate the optimality of some existing MPC protocols in terms of bottleneck complexity or the amount of correlated randomness.

IACR Communications in Cryptology•Jan 8, 2026•0 citations

Efficient Construction of Secure Multiparty Computation Realizing Practical Functionality

礼央 江利口

Secure multiparty computation (MPC) is a fundamental cryptographic primitive for a set of players to interactively compute a function without revealing their private inputs.MPC is of theoretical and practical importance due to its many interesting applications including voting, sealed-bid auctions and privacy-preserving machine learning.It has been an active research area in cryptography and many different approaches have been proposed to enhance security, functionality and efficiency in the literature.In particular, there are general constructions proving the existence of MPC for arbitrary functions under a set of desirable security notions.However, these general results do not give a satisfactory solution to constructing concrete protocols that are efficient enough to use in practice.It is therefore more effective to give concrete and efficient constructions of MPC protocols tailored to specific functionalities and security notions required in practical applications.In this thesis, we study different approaches to realize efficient MPC for functionalities of practical importance with enhanced security notions including non-threshold adversary structures and malicious security.We attain improvement in communication and round complexity by focusing on specific classes of functions or limited but still non-threshold adversary structures.The main contributions of this thesis consist of five parts, which concern the following specific MPC tasks: non-interactive MPC (NIMPC) for symmetric functions and linear classifiers, homomorphic secret sharing (HSS) for low-degree polynomials, verifiably multiplicative secret sharing (VMSS), private information retrieval (PIR), and distributed noise generation for differential privacy.Concretely, we first propose efficient constructions of NIMPC protocols tailored to symmetric functions and linear classifiers.Our protocols improve the best-known communication complexity of existing protocols.In addition, we reveal that a previously proposed method to enhance security of NIMPC does not satisfy specified security requirements and we also fix the problem.Secondly, we propose constructions of HSS schemes that tolerate multipartite and general adversary structures assuming homomorphic encryption.Our schemes support parallel evaluation of a single low-degree polynomial and hence achieve better communication complexity than if we simply execute the previous HSS schemes in parallel.Thirdly, we present VMSS schemes tolerating multipartite adversary structures.Our schemes have smaller communication complexity than those obtained from the previous constructions applicable to general adversary structures.In the fourth part, we study the optimal communication complexity of error-correcting PIR.We asymptotically characterize it as a function of the database size and as a corollary, obtain more communication-efficient error-correcting PIR schemes than the previous ones.Finally, we provide three kinds of MPC protocols for generating noise drawn from probability distributions providing differential privacy.We improve the round or communication complexity of the previous protocols for distributed noise generation.We also extend our protocols so that they provide differential privacy against malicious adversaries.

•Mar 23, 2023•0 citations

Round-Optimal Secure Multiparty Computation from Minimal Assumptions

Akshayaram Srinivasan

Secure Multiparty Computation (MPC) allows a set of parties, each having its own private data, to compute a function of their joint data such that the parties only learn the output of this function and everything else about their data is hidden. MPC is a fundamental cryptographic abstraction that captures many other natural cryptographic primitives as special cases. It also has a wide range of practical applications such as conducting secure electronic auctions, delegating sensitive computation to untrusted cloud service providers, secure computation on genomic data and training machine learning models on private data.A long-standing open problem in this area is to construct MPC protocols that have {\\it optimal} (two-round) round complexity under the {\\it weakest} possible cryptographic hardness assumptions.We {\\it completely resolve} this problem by showing lower bounds and matching upper bounds on the hardness assumptions required for constructing round-optimal MPC. Specifically, we obtain the following results.\\begin{itemize}\\item \\textbf{Black-Box Separation.} We show that there exists no construction of two-round semi-honest MPC protocol for general functions that makes black-box use of a two-round oblivious transfer. As a corollary, a similar separation holds when starting with any 2-party functionality other than oblivious transfer. \\item \\textbf{Non-Black-Box Construction.} We show that the above negative result can be bypassed by making non-black-box use of a two-round oblivious transfer. Specifically, starting from a semi-honest (resp. malicious) secure two-round oblivious transfer protocol, we construct a two-round MPC protocol against semi-honest (resp. malicious) adversaries. \\end{itemize}Since any two-round MPC protocol for general functionalities implies a two-round oblivious transfer as a special case, the above two results show that non-black-box use of oblivious transfer is {\\it necessary and sufficient} to construct round-optimal MPC protocols.

•Jan 1, 2020•0 citations

On the (in)efficiency of non-interactive secure multiparty computation

Maki Yoshida, Satoshi Obana

Secure multi-party computation (MPC) enables multiple players to cooperatively evaluate various functions in the presence of adversaries. In this paper, we consider non-interactive MPC (NIMPC) against honest-but-curious adversaries in the information-theoretic setting, which was introduced by Beimel et al. at CRYPTO 2014. Their main focus is to realize stronger security while completely avoiding interaction, and succeeded to show that every function admits a fully robust NIMPC protocol. In this paper, we further develop the study of NIMPC. We first present a simple lower bound on the communication complexity derived from the correctness requirement of NIMPC. Secondly, we present an efficient NIMPC protocol for indicator functions, which is an important building block of NIMPC protocols. An NIMPC protocol for arbitrary functions is also constructed from the proposed NIMPC for indicator functions by using the generic compiler introduced by Beimel et al. in CRYPTO 2014. The communication complexities of NIMPC protocols presented in this paper are much more efficient than the previous ones. In fact, the gap between the lower and upper bounds of the communication complexity is reduced from exponential in the input length to quadratic . Finally, we show some improvements on the efficiency in the so-called offline-online model. Specifically, for some sets of functions, the exponential amount of offline communication reduces the online communication to almost optimum amount in the standard model.

Designs Codes and Cryptography•Mar 26, 2018•7 citations
The bottleneck-complexity (BC) of secure multiparty computation (MPC) protocols is a measure of the maximum number of bits which are sent and received by any party in protocol. As the name suggests, the goal of studying BC-efficient protocols is to increase overall efficiency by making sure that the workload in the protocol is somehow "amortized" by the protocol participants. Orlandi et al. [Orlandi et al., 2022] initiated the study of BC-efficient protocols from simple assumptions in the correlated randomness model and for semi-honest adversaries. In this work, we extend the study of [Orlandi et al., 2022] in two primary directions: (a) to a larger and more general class of functions and (b) to the information-theoretic setting. In particular, we offer semi-honest secure protocols for the useful function classes of abelian programs, "read-k" non-abelian programs, and "read-k" generalized formulas. Our constructions use a novel abstraction, called incremental function secret-sharing (IFSS), that can be instantiated with unconditional security or from one-way functions (with different efficiency trade-offs).
In this work, we initiate the study of bottleneck complexity as a new communication efficiency measure for secure multiparty computation (MPC). Roughly, the bottleneck complexity of an MPC protocol is defined as the maximum communication complexity required by any party within the protocol execution. We observe that even without security, bottleneck communication complexity is an interesting measure of communication complexity for (distributed) functions and propose it as a fundamental area to explore. While achieving O(n) bottleneck complexity (where n is the number of parties) is straightforward, we show that: (1) achieving sublinear bottleneck complexity is not always possible, even when no security is required. (2) On the other hand, several useful classes of functions do have o(n) bottleneck complexity, when no security is required. Our main positive result is a compiler that transforms any (possibly insecure) efficient protocol with fixed communication-pattern for computing any functionality into a secure MPC protocol while preserving the bottleneck complexity of the underlying protocol (up to security parameter overhead). Given our compiler, an efficient protocol for any function f with sublinear bottleneck complexity can be transformed into an MPC protocol for f with the same bottleneck complexity. Along the way, we build cryptographic primitives - incremental fully-homomorphic encryption, succinct non-interactive arguments of knowledge with ID-based simulation-extractability property and verifiable protocol execution - that may be of independent interest.
Multiparty computation (MPC) is a powerful and generic cryptographic framework capable of realizing essentially any cryptographic task (functionality) while preserving privacy and robustness. In the MPC model, a group of mutually distrustful parties seek to jointly compute a function f of their privately held inputs x1, ..., xn, while revealing no information about those inputs beyond what is entailed by the function output(s). Some portion of these players may be corrupted, controlled by a centralized adversary who directs their (mis)behavior and seeks to gain information on private inputs or to disrupt the protocol execution. In this work, we examine the resource requirements of information-theoretically secure multiparty computation. In particular, we look at trade-offs involving what we call assumptions, by which we mean two aspects of the model's setup: (1) the extent to which parties are connected by secure, pairwise communication channels; and (2) the usage (as a black box) of a channel—a primitive which enforces consistency among views by allowing a single party to send a message to all other parties which is guaranteed to be consistent, even if the broadcaster is corrupted. Part I of this work focuses on the first network-model assumption, that of the graph's connectivity by pairwise channels. We show upper and lower bounds on communication complexity in the Secure Message Transmission with Public Discussion (SMT-PD) model, as a function of the threshold of corrupted parties. The SMT-PD model, which abstracts the problem of secure communication over a partially connected network, includes two components: a public and a set of simple channels. We show significant improvements in both areas: on the channel, we reduce communication to logarithmic in terms of the message's bit-length m, where the previous best result was linear in m; on the simple channels, we reduce from O(mn) to O(mn/(n−t)), where n is the number of simple channels and t is a bound on the number of corrupted channels. Using tools from information theory, we show this amount of simple-wire communication is essentially optimal. Finally, we give an amortized solution which drastically improves communication over channel when the protocol is repeated many times sequentially. Part II shifts focus to the second network-model assumption, the use of an atomic broadcast primitive. Here we show that three broadcast rounds suffice for general secure computation, while two broadcast rounds are necessary. In particular we show that even for the natural and important functionality of Weak Secret Sharing—a type of distributed commitment—there is no protocol which uses only a single broadcast and achieves better than an explicit constant probability of success (so the protocol's success cannot be a function of a security parameter).
Secure multiparty computation (MPC) is a cryptographic primitive which enables multiple parties to jointly compute a function without revealing any extra information on their private inputs. Bottleneck complexity is an efficiency measure that captures the load-balancing aspect of MPC protocols, defined as the maximum amount of communication required by any party. In this work, we study the problem of establishing lower bounds on the bottleneck complexity of MPC protocols. While the previously known techniques for lower bounding total communication complexity can also be applied to bottleneck complexity, they do not provide nontrivial bounds in the correlated randomness model, which is commonly assumed by existing protocols achieving low bottleneck complexity, or they are applied only to functions of limited practical interest. We propose several novel techniques for lower bounding the bottleneck complexity of MPC protocols. Our methods derive nontrivial lower bounds even in the correlated randomness model and apply to practically relevant functions including the sum function and threshold functions. Furthermore, our lower bounds demonstrate the optimality of some existing MPC protocols in terms of bottleneck complexity or the amount of correlated randomness.
Secure multiparty computation (MPC) is a fundamental cryptographic primitive for a set of players to interactively compute a function without revealing their private inputs.MPC is of theoretical and practical importance due to its many interesting applications including voting, sealed-bid auctions and privacy-preserving machine learning.It has been an active research area in cryptography and many different approaches have been proposed to enhance security, functionality and efficiency in the literature.In particular, there are general constructions proving the existence of MPC for arbitrary functions under a set of desirable security notions.However, these general results do not give a satisfactory solution to constructing concrete protocols that are efficient enough to use in practice.It is therefore more effective to give concrete and efficient constructions of MPC protocols tailored to specific functionalities and security notions required in practical applications.In this thesis, we study different approaches to realize efficient MPC for functionalities of practical importance with enhanced security notions including non-threshold adversary structures and malicious security.We attain improvement in communication and round complexity by focusing on specific classes of functions or limited but still non-threshold adversary structures.The main contributions of this thesis consist of five parts, which concern the following specific MPC tasks: non-interactive MPC (NIMPC) for symmetric functions and linear classifiers, homomorphic secret sharing (HSS) for low-degree polynomials, verifiably multiplicative secret sharing (VMSS), private information retrieval (PIR), and distributed noise generation for differential privacy.Concretely, we first propose efficient constructions of NIMPC protocols tailored to symmetric functions and linear classifiers.Our protocols improve the best-known communication complexity of existing protocols.In addition, we reveal that a previously proposed method to enhance security of NIMPC does not satisfy specified security requirements and we also fix the problem.Secondly, we propose constructions of HSS schemes that tolerate multipartite and general adversary structures assuming homomorphic encryption.Our schemes support parallel evaluation of a single low-degree polynomial and hence achieve better communication complexity than if we simply execute the previous HSS schemes in parallel.Thirdly, we present VMSS schemes tolerating multipartite adversary structures.Our schemes have smaller communication complexity than those obtained from the previous constructions applicable to general adversary structures.In the fourth part, we study the optimal communication complexity of error-correcting PIR.We asymptotically characterize it as a function of the database size and as a corollary, obtain more communication-efficient error-correcting PIR schemes than the previous ones.Finally, we provide three kinds of MPC protocols for generating noise drawn from probability distributions providing differential privacy.We improve the round or communication complexity of the previous protocols for distributed noise generation.We also extend our protocols so that they provide differential privacy against malicious adversaries.
Secure Multiparty Computation (MPC) allows a set of parties, each having its own private data, to compute a function of their joint data such that the parties only learn the output of this function and everything else about their data is hidden. MPC is a fundamental cryptographic abstraction that captures many other natural cryptographic primitives as special cases. It also has a wide range of practical applications such as conducting secure electronic auctions, delegating sensitive computation to untrusted cloud service providers, secure computation on genomic data and training machine learning models on private data.A long-standing open problem in this area is to construct MPC protocols that have {\\it optimal} (two-round) round complexity under the {\\it weakest} possible cryptographic hardness assumptions.We {\\it completely resolve} this problem by showing lower bounds and matching upper bounds on the hardness assumptions required for constructing round-optimal MPC. Specifically, we obtain the following results.\\begin{itemize}\\item \\textbf{Black-Box Separation.} We show that there exists no construction of two-round semi-honest MPC protocol for general functions that makes black-box use of a two-round oblivious transfer. As a corollary, a similar separation holds when starting with any 2-party functionality other than oblivious transfer. \\item \\textbf{Non-Black-Box Construction.} We show that the above negative result can be bypassed by making non-black-box use of a two-round oblivious transfer. Specifically, starting from a semi-honest (resp. malicious) secure two-round oblivious transfer protocol, we construct a two-round MPC protocol against semi-honest (resp. malicious) adversaries. \\end{itemize}Since any two-round MPC protocol for general functionalities implies a two-round oblivious transfer as a special case, the above two results show that non-black-box use of oblivious transfer is {\\it necessary and sufficient} to construct round-optimal MPC protocols.
Secure multi-party computation (MPC) enables multiple players to cooperatively evaluate various functions in the presence of adversaries. In this paper, we consider non-interactive MPC (NIMPC) against honest-but-curious adversaries in the information-theoretic setting, which was introduced by Beimel et al. at CRYPTO 2014. Their main focus is to realize stronger security while completely avoiding interaction, and succeeded to show that every function admits a fully robust NIMPC protocol. In this paper, we further develop the study of NIMPC. We first present a simple lower bound on the communication complexity derived from the correctness requirement of NIMPC. Secondly, we present an efficient NIMPC protocol for indicator functions, which is an important building block of NIMPC protocols. An NIMPC protocol for arbitrary functions is also constructed from the proposed NIMPC for indicator functions by using the generic compiler introduced by Beimel et al. in CRYPTO 2014. The communication complexities of NIMPC protocols presented in this paper are much more efficient than the previous ones. In fact, the gap between the lower and upper bounds of the communication complexity is reduced from exponential in the input length to quadratic . Finally, we show some improvements on the efficiency in the so-called offline-online model. Specifically, for some sets of functions, the exponential amount of offline communication reduces the online communication to almost optimum amount in the standard model.