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

Unconditionally Secure Multiparty Set Intersection Re-Visited.

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan

Published Jan 1, 2008• 0 citations
OpenAlex

Abstract

Abstract. In this paper, we re-visit the problem of unconditionally secure multiparty set intersection in information theoretic model. Li et.al [24] have proposed a protocol for n-party set intersection problem, which players are corrupted by an active adversary having unbounded computing power. Moreover, they have claimed that their protocol takes six rounds of communication and incurs a communication complexity of O(n 4 m 2), where each player has a set of size m. However, we show that the round complexity and communication complexity of the protocol in [24] is much more than what is claimed in [24]. We then propose a novel unconditionally secure protocol for multiparty set intersection problem with n> 3t players, which significantly improves the ”actual ” round and communication complexity (as shown in this paper) of the protocol given in [24]. To design our protocol, we use several tools which are of independent interest. provides unconditional security when t < n 3

Related papers

On the Hardness of Information-Theoretic Multiparty Computation

Yuval Ishai, Eyal Kushilevitz Z

Abstract We revisit the following open problem in information-theoretic cryptography: Does the communication complexity of unconditionally secure computation depend on the computational complexity of the function being computed? For instance, can computationally unbounded players compute an arbitrary function of their inputs with polynomial communication complexity and a linear threshold of unconditional privacy? Can this be done using a constant number of communication rounds? We provide an explanation for the difficulty of resolving these questions by showing that they are closely related to the problem of obtaining efficient protocols for (information-theoretic) private information retrieval and hence also to the problem of constructing short locally-decodable error-correcting codes. The latter is currently considered to be among the most intriguing open problems in complexity theory. Keywords. Information-theoretic cryptography, secure multiparty computation, private information retrieval, locally decodable codes. 1 Introduction In STOC 1990, Beaver, Micali, and Rogaway [5] posed the following question: Is there a constant-round protocol that allows k computationally unbounded players to defeat a computationally unbounded adversary, while using only a polynomial amount of communication in the total length of their inputs?

•Jan 1, 2004•0 citations

Unconditionally Secure Asynchronous Multiparty Computation with Linear Communication Complexity

Ashish Choudhury, Martin Hirt, Arpita Patra

Unconditionally secure multiparty computation (MPC) allows a set of n mutually distrusting parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can actively corrupt any t out of the n parties. Designing an asynchronous MPC (AMPC) protocol with a communication complexity of O(n) field elements per multiplication gate is a long standing open problem. We solve the open problem by presenting two AMPC protocols with the corruption threshold t < n/4. Our first protocol is statistically secure (i.e. involves a negligible error in the protocol outcome) in a completely asynchronous setting and improves the communication complexity of the previous best AMPC protocol in the same setting by a factor of Θ(n). Our second protocol is perfectly secure (i.e. error free) in a hybrid setting, where one round of communication is assumed to be synchronous and improves the communication complexity of the previous best AMPC protocol in the hybrid setting by a factor of Θ(n 2). Starting with the seminal work of Beaver (CRYPTO 1991), it is by now a well-known technique to evaluate multiplication gates in an MPC protocol using shared random multiplication triples. The central contribution common to both the presented protocols is a new and simple framework for generating shared random multiplication triples. All the existing protocols approach the problem by first producing shared pairs of random values, followed by computing

•Jan 17, 2013•2 citations

(Unconditional) Secure Multiparty Computation with Man-in-the-middle Attacks

Shailesh Vaya

In secure multi-party computation $n$ parties jointly evaluate an $n$-variate function $f$ in the presence of an adversary which can corrupt up till $t$ parties. Almost all the works that have appeared in the literature so far assume the presence of authenticated channels between the parties. This assumption is far from realistic. Two directions of research have been borne from relaxing this (strong) assumption: (a) The adversary is virtually omnipotent and can control all the communication channels in the network, (b) Only a partially connected topology of authenticated channels is guaranteed and adversary controls a subset of the communication channels in the network. This work introduces a new setting for (unconditional) secure multiparty computation problem which is an interesting intermediate model with respect to the above well studied models from the literature (by sharing a salient feature from both the above models). We consider the problem of (unconditional) secure multi-party computation when 'some' of the communication channels connecting the parties can be corrupted passively as well as actively. For this setting, some honest parties may be connected to several other honest parties via corrupted channels and may not be able to authentically communicate with them. Such parties may not be assured the canonical guarantees of correctness or privacy. We present refined definitions of security for this new intermediate model of unconditional multiparty computation. We show how to adapt protocols for (Unconditional) secure multiparty computation to realize the definitions and also argue the tightness of the results achieved by us.

arXiv:1005.5020•May 27, 2010•0 citations

Broadcast-Efficient Secure Multiparty Computation.

Juan A. Garay, Clint Givens, Rafail Ostrovsky

Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource

•Jan 1, 2012•3 citations

Trading Correctness for Privacy in Unconditional Multi-Party Computation

Matthias Fitzi, Martin Hirt, Ueli M. Maurer

. This paper improves on the classical results in unconditionally secure multi-party computation among a set of n players, by considering a model with three simultaneously occurring types of player corruption: the adversary can actively corrupt (i.e. take full control over) up to ta players and, additionally, can passively corrupt (i.e. read the entire information of) up to tp players and fail-corrupt (i.e. stop the computation of) up to tf other players. The classical results in multi-party computation are for the special cases of only passive (ta = tf = 0) or only active (tp = tf = 0) corruption. In the passive case, every function can be computed securely if and only if tp ! n=2. In the active case, every function can be computed securely if and only if ta ! n=3; when a broadcast channel is available, then this bound is ta ! n=2. These bounds are tight. Strictly improving these results, one of our results states that, in addition to tolerating ta ! n=3 actively corrupted players, pr...

•Jan 1, 1998•5 citations

Communication-Efficient MPC for General Adversary Structures

Joshua Lampkins, Rafail Ostrovsky

Abstract. A multiparty computation (MPC) protocol allows a set of players to compute a function of their inputs while keeping the inputs private and at the same time securing the correctness of the output. Most MPC protocols assume that the adversary can corrupt up to a fixed fraction of the number of players. Hirt and Maurer initiated the study of MPC under more general corruption patterns, in which the adversary is allowed to corrupt any set of players in some pre-defined collection of sets [6]. In this paper we consider this important direction of research and present significantly improved communication complexity of MPC protocols for general adversary structures. More specifically, ours is the first unconditionally secure protocol that achieves linear communication in the size of Monotone Span Program representing the adversary structure in the malicious setting against any Q2 adversary structure, whereas all previous protocols were at least cubic.

•Jan 1, 2013•0 citations
Abstract. In this paper, we re-visit the problem of unconditionally secure multiparty set intersection in information theoretic model. Li et.al [24] have proposed a protocol for n-party set intersection problem, which players are corrupted by an active adversary having unbounded computing power. Moreover, they have claimed that their protocol takes six rounds of communication and incurs a communication complexity of O(n 4 m 2), where each player has a set of size m. However, we show that the round complexity and communication complexity of the protocol in [24] is much more than what is claimed in [24]. We then propose a novel unconditionally secure protocol for multiparty set intersection problem with n> 3t players, which significantly improves the ”actual ” round and communication complexity (as shown in this paper) of the protocol given in [24]. To design our protocol, we use several tools which are of independent interest. provides unconditional security when t < n 3
Abstract We revisit the following open problem in information-theoretic cryptography: Does the communication complexity of unconditionally secure computation depend on the computational complexity of the function being computed? For instance, can computationally unbounded players compute an arbitrary function of their inputs with polynomial communication complexity and a linear threshold of unconditional privacy? Can this be done using a constant number of communication rounds? We provide an explanation for the difficulty of resolving these questions by showing that they are closely related to the problem of obtaining efficient protocols for (information-theoretic) private information retrieval and hence also to the problem of constructing short locally-decodable error-correcting codes. The latter is currently considered to be among the most intriguing open problems in complexity theory. Keywords. Information-theoretic cryptography, secure multiparty computation, private information retrieval, locally decodable codes. 1 Introduction In STOC 1990, Beaver, Micali, and Rogaway [5] posed the following question: Is there a constant-round protocol that allows k computationally unbounded players to defeat a computationally unbounded adversary, while using only a polynomial amount of communication in the total length of their inputs?
Unconditionally secure multiparty computation (MPC) allows a set of n mutually distrusting parties to securely compute an agreed function f over some finite field in the presence of a computationally unbounded adversary, who can actively corrupt any t out of the n parties. Designing an asynchronous MPC (AMPC) protocol with a communication complexity of O(n) field elements per multiplication gate is a long standing open problem. We solve the open problem by presenting two AMPC protocols with the corruption threshold t < n/4. Our first protocol is statistically secure (i.e. involves a negligible error in the protocol outcome) in a completely asynchronous setting and improves the communication complexity of the previous best AMPC protocol in the same setting by a factor of Θ(n). Our second protocol is perfectly secure (i.e. error free) in a hybrid setting, where one round of communication is assumed to be synchronous and improves the communication complexity of the previous best AMPC protocol in the hybrid setting by a factor of Θ(n 2). Starting with the seminal work of Beaver (CRYPTO 1991), it is by now a well-known technique to evaluate multiplication gates in an MPC protocol using shared random multiplication triples. The central contribution common to both the presented protocols is a new and simple framework for generating shared random multiplication triples. All the existing protocols approach the problem by first producing shared pairs of random values, followed by computing
In secure multi-party computation nnn parties jointly evaluate an nnn-variate function fff in the presence of an adversary which can corrupt up till ttt parties. Almost all the works that have appeared in the literature so far assume the presence of authenticated channels between the parties. This assumption is far from realistic. Two directions of research have been borne from relaxing this (strong) assumption: (a) The adversary is virtually omnipotent and can control all the communication channels in the network, (b) Only a partially connected topology of authenticated channels is guaranteed and adversary controls a subset of the communication channels in the network. This work introduces a new setting for (unconditional) secure multiparty computation problem which is an interesting intermediate model with respect to the above well studied models from the literature (by sharing a salient feature from both the above models). We consider the problem of (unconditional) secure multi-party computation when 'some' of the communication channels connecting the parties can be corrupted passively as well as actively. For this setting, some honest parties may be connected to several other honest parties via corrupted channels and may not be able to authentically communicate with them. Such parties may not be assured the canonical guarantees of correctness or privacy. We present refined definitions of security for this new intermediate model of unconditional multiparty computation. We show how to adapt protocols for (Unconditional) secure multiparty computation to realize the definitions and also argue the tightness of the results achieved by us.
Secure multiparty computation (MPC) is perhaps the most popular paradigm in the area of cryptographic protocols. It allows several mutually untrustworthy parties to jointly compute a function of their private inputs, without revealing to each other information about those inputs. In the case of unconditional (information-theoretic) security, protocols are known which tolerate a dishonest minority of players, who may coordinate their attack and deviate arbitrarily from the protocol specification. It is typically assumed in these results that parties are connected pairwise by authenticated, private channels, and that in addition they have access to a “broadcast ” channel. Broadcast allows one party to send a consistent message to all other parties, guaranteeing consistency even if the broadcaster is corrupted. Because broadcast cannot be simulated on the point-to-point network when more than a third of the parties are corrupt, it is impossible to construct general MPC protocols in this setting without using a broadcast channel (or some equivalent addition to the model). A great deal of research has focused on increasing the efficiency of MPC, primarily in terms of round complexity and communication complexity. In this work we propose a refinement of the round complexity which we term broadcast complexity. We view the broadcast channel as an expensive resource
. This paper improves on the classical results in unconditionally secure multi-party computation among a set of n players, by considering a model with three simultaneously occurring types of player corruption: the adversary can actively corrupt (i.e. take full control over) up to ta players and, additionally, can passively corrupt (i.e. read the entire information of) up to tp players and fail-corrupt (i.e. stop the computation of) up to tf other players. The classical results in multi-party computation are for the special cases of only passive (ta = tf = 0) or only active (tp = tf = 0) corruption. In the passive case, every function can be computed securely if and only if tp ! n=2. In the active case, every function can be computed securely if and only if ta ! n=3; when a broadcast channel is available, then this bound is ta ! n=2. These bounds are tight. Strictly improving these results, one of our results states that, in addition to tolerating ta ! n=3 actively corrupted players, pr...
Abstract. A multiparty computation (MPC) protocol allows a set of players to compute a function of their inputs while keeping the inputs private and at the same time securing the correctness of the output. Most MPC protocols assume that the adversary can corrupt up to a fixed fraction of the number of players. Hirt and Maurer initiated the study of MPC under more general corruption patterns, in which the adversary is allowed to corrupt any set of players in some pre-defined collection of sets [6]. In this paper we consider this important direction of research and present significantly improved communication complexity of MPC protocols for general adversary structures. More specifically, ours is the first unconditionally secure protocol that achieves linear communication in the size of Monotone Span Program representing the adversary structure in the malicious setting against any Q2 adversary structure, whereas all previous protocols were at least cubic.