### Information Theoretically Secure Multi Party Set Intersection Re-Visited

Arpita Patra, 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.

Available format(s)
Publication info
Published elsewhere. Unknown where it was published
Keywords
Multiparty ComputationInformation Theoretic SecurityError Probability
Contact author(s)
arpitapatra_10 @ yahoo co in
History
2009-05-22: revised
See all versions
Short URL
https://ia.cr/2009/116

CC BY

BibTeX

@misc{cryptoeprint:2009/116,
author = {Arpita Patra and Ashish Choudhary and C.  Pandu Rangan},
title = {Information Theoretically Secure Multi Party Set Intersection Re-Visited},
howpublished = {Cryptology ePrint Archive, Paper 2009/116},
year = {2009},
note = {\url{https://eprint.iacr.org/2009/116}},
url = {https://eprint.iacr.org/2009/116}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.