Unconditionally Secure Multiparty Set Intersection Re-Visited

Arpita Patra; Ashish Choudhary; C.  Pandu Rangan

Paper 2008/462

Unconditionally Secure Multiparty Set Intersection Re-Visited

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

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. NIL
Contact author(s): arpitapatra_10 @ yahoo co in
History: 2008-12-25: revised; 2008-11-02: received; See all versions
Short URL: https://ia.cr/2008/462
License: CC BY

BibTeX

@misc{cryptoeprint:2008/462,
      author = {Arpita Patra and Ashish Choudhary and C.  Pandu Rangan},
      title = {Unconditionally Secure Multiparty Set Intersection Re-Visited},
      howpublished = {Cryptology ePrint Archive, Paper 2008/462},
      year = {2008},
      note = {\url{https://eprint.iacr.org/2008/462}},
      url = {https://eprint.iacr.org/2008/462}
}