An Unconditionally Secure Protocol for Multi-Party Set Intersection

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan

Ferhat Karakoç, Alptekın Küpçü

Arpita Patra, Ashish Choudhary, Chandrasekharan Pandu Rangan

Abstract. In this paper, we re-visit the problem of unconditionally secure multiparty set intersection in information theoretic model. Li et.al [24] have proposed a protocol for n-party set intersection problem, which players are corrupted by an active adversary having unbounded computing power. Moreover, they have claimed that their protocol takes six rounds of communication and incurs a communication complexity of O(n 4 m 2), where each player has a set of size m. However, we show that the round complexity and communication complexity of the protocol in [24] is much more than what is claimed in [24]. We then propose a 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 [24]. To design our protocol, we use several tools which are of independent interest. provides unconditional security when t < n 3

Michele Ciampi, Claudio Orlandi

Yu Yu, Jussipekka Leiwo, A. Benjamin Premkumar

Yaohua Lu, Gangyi Ding

Secure multi-party computation (SMC) enables multiple parties to collaboratively perform computational tasks without revealing their private data. A specific application scenario within SMC is Private Set Intersection with Correlated Sum (PSI-CS), where two participating parties compute the sum of associated elements in their intersection while preserving the privacy of their individual sets. This problem arises in various contexts, including calculating conversion amounts between suppliers and platforms, such as advertising conversion amounts and agency business conversion amounts. The paper proposes a protocol that employs quantum single-photon technology to compute the PSI-CS, provides four technical solutions suitable for various scenarios ranging from small to large data volumes, sparse to dense datasets, and without revealing the cardinality of the intersection. Additionally, the method extends to computing the union set with correlated sums. We experimentally validate the proposed protocol, conduct correctness and security analyses, and demonstrate its practical significance and application value. By utilizing single-photon technology, quantum gate operations, and measurements become more accessible, simplifying the protocol’s implementation. Notably, our approach provides unconditional security against quantum computational attacks, representing a substantial improvement in both efficiency and practical applicability compared to classical domain protocols.