An Effective Multiple Private Set Intersection
摘要
Private set intersection (PSI) is a hot topic in terms of privacy preservation. While numerous studies have focused on two-party PSI, there remains a notable lack of research on multiple PSI scenarios. In fact, as both parties continue to add new datasets, the need for multiple PSI often arises, accompanied by a significant overhead due to the accumulated datasets. We propose a multiple PSI protocol with semi-honest security. Based on the protocol (Pinkas et al., Crypto 2019, spot-low method), we design a streaming PSI, and every time the newly added dataset accumulates to a certain threshold, the streaming PSI are generated, leading to a notable decrease in overall overhead for the subsequent PSI. To our knowledge, this is the first protocol specifically designed for multiple PSI scenarios. Our experiments demonstrate that our protocol achieves optimal performance in terms of runtime and communication. For instance, when the initial dataset size is \(2^{24}\) and the newly added dataset size is \(2^{16}\) in both parties. Then for the second PSI, the dataset size is \((2^{24}+2^{16})\) in both parties, our runtime is reduced to 14.6 s, and our communication overhead is reduced to 4.8MB.