Cryptology ePrint Archive: Report 2009/116

Information Theoretically Secure Multi Party Set Intersection Re-Visited

Arpita Patra and Ashish Choudhary and C. Pandu Rangan

Abstract: We re-visit the problem of secure multiparty set intersection in information theoretic settings. In \cite{LiSetMPCACNS07}, Li et.al have proposed a protocol for multiparty set intersection problem with $n$ parties, that provides information theoretic security, when $t < \frac{n}{3}$ parties are corrupted by an active adversary having {\it unbounded computing power}. In \cite{LiSetMPCACNS07}, the authors claimed that their protocol takes six rounds of communication and communicates ${\cal O}(n^4m^2)$ field elements, where each party has a set containing $m$ field elements. However, we show that the round 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} information theoretically secure protocol for multiparty set intersection with $n > 3t$, 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.

Category / Keywords: Multiparty Computation, Information Theoretic Security, Error Probability

Date: received 11 Mar 2009, last revised 22 May 2009

Contact author: arpitapatra_10 at yahoo co in

Available format(s): PDF | BibTeX Citation

Version: 20090522:063742 (All versions of this report)

Short URL: ia.cr/2009/116

Discussion forum: Show discussion | Start new discussion