# zbMATH — the first resource for mathematics

Information theoretically secure multi party set intersection re-visited. (English) Zbl 1267.94090
Jacobson, Michael J. jun. (ed.) et al., Selected areas in cryptography. 16th annual international workshop, SAC 2009, Calgary, Alberta, Canada, August 13–14, 2009. Revised selected papers. Berlin: Springer (ISBN 978-3-642-05443-3/pbk). Lecture Notes in Computer Science 5867, 71-91 (2009).
Summary: We re-visit the problem of secure multiparty set intersection (MPSI) in information-theoretic settings. In [Lect. Notes Comput. Sci. 4521, 226–236 (2007; Zbl 1214.94050)], R. Li and C. Wu have proposed a protocol for MPSI with $$n = 3t + 1$$ parties, that provides information theoretic security, when $$t$$ out of those $$n$$ parties are corrupted by an active adversary having unbounded computing power. In [loc. cit.], it was claimed that their protocol takes six rounds of communication and communicates $${\mathcal 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 [loc. cit.] is much more than what is claimed in [loc. cit.]. We then propose a novel information theoretically secure protocol for MPSI with $$n \geq 3t + 1$$, which significantly improves the “actual” round and communication complexity of the protocol of [loc. cit.]. Our protocols employ several tools which are of independent interest.
For the entire collection see [Zbl 1177.94012].

##### MSC:
 94A60 Cryptography
##### Keywords:
multiparty computation; information-theoretic security
Full Text: