Unconditionally Secure Multiparty Set Intersection Re-Visited.
Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan
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
•Jan 1, 2008•0 citations