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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

An Effective Multiple Private Set Intersection

  • Qiang Liu,
  • Xiaojun Chen,
  • Weizhan Jing,
  • Ye Dong

摘要

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.