Welcome to the resource topic for 2008/462
Title:
Unconditionally Secure Multiparty Set Intersection Re-Visited
Authors: Arpita Patra, Ashish Choudhary, C. Pandu Rangan
Abstract:In this paper, we re-visit the problem of unconditionally secure multiparty set intersection in information theoretic model. Li et.al \cite{LiSetMPCACNS07} have proposed a protocol for n-party set intersection problem, which provides unconditional security when t < \frac{n}{3} players are corrupted by an active adversary having {\it unbounded computing power}. Moreover, they have claimed that their protocol takes six rounds of communication and incurs a communication complexity of {\cal O}(n^4m^2), where each player has a set of size m. However, we show that the round complexity and communication complexity of the protocol in \cite{LiSetMPCACNS07} is much more than what is claimed in \cite{LiSetMPCACNS07}. We then propose a {\it 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 \cite{LiSetMPCACNS07}. To design our protocol, we use several tools which are of independent interest.
ePrint: https://eprint.iacr.org/2008/462
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .