Multi-Party Private Set Intersection: An Information-Theoretic Approach
Multi-Party Private Set Intersection: An Information-Theoretic Approach
复制标题
DOI：
10.1109/jsait.2021.3057597
复制
发表时间：
2020-08
期刊：
影响因子：
--
通讯作者：
Zhusheng Wang;Karim A. Banawan;S. Ulukus
中科院分区：
文献类型：
--
作者：
Zhusheng Wang;Karim A. Banawan;S. Ulukus
研究了多方私有集交(MP-PSI)问题。在MP-PSI中，有$M$方，每个方在$N_{i}$复制和非合谋数据库上存储一个数据集${\mathcal{P}}_{i}$，我们想要计算数据集$\Cap_{i=1}^{M}{\mathcal{P}}_{i}$的交集，而不将集合交集之外的任何信息泄漏给任何一方。我们考虑一种特定的通信协议，其中称为领导者方的一方通过向称为客户端方的其余方发送查询来发起MP-PSI协议。客户方不允许相互通信。我们提出了一个信息论方案，它秘密地计算交集$\cap{i=1}^{M}{\mathcal{P}}_{i}$，下载代价为$D=\min_{t\in\1，ldots，M\}\sum_{i\in\{1，ldots，M\}\setminus{t}\lceil\frac{|{\mathcal{P}}_{t}|N_{i}}{N_{i}-1}\rceil$。类似于两方PSI问题，我们的方案建立在PSI问题和多消息对称私人信息检索(MM-SPIR)问题之间的联系之上。我们的方案是两方PSI方案的非平凡推广，因为它需要共享公共随机性的复杂设计。有趣的是，在下载成本方面，由于MP-PSI问题中的隐私约束比两方PSI问题更严格，所以我们的方案不会招致任何惩罚。
We investigate the problem of multi-party private set intersection (MP-PSI). In MP-PSI, there are $M$ parties, each storing a data set ${\mathcal {P}}_{i}$ over $N_{i}$ replicated and non-colluding databases, and we want to calculate the intersection of the data sets $\cap _{i=1}^{M} {\mathcal {P}}_{i}$ without leaking any information beyond the set intersection to any of the parties. We consider a specific communication protocol where one of the parties, called the leader party, initiates the MP-PSI protocol by sending queries to the remaining parties which are called client parties. The client parties are not allowed to communicate with each other. We propose an information-theoretic scheme that privately calculates the intersection $\cap _{i=1}^{M} {\mathcal {P}}_{i}$ with a download cost of $D = \min _{t \in \{1,\ldots, M\}} \sum _{i \in \{1,\ldots, M\}\setminus {t}} \lceil \frac {| {\mathcal {P}}_{t}|N_{i}}{N_{i}-1}\rceil $ . Similar to the 2-party PSI problem, our scheme builds on the connection between the PSI problem and the multi-message symmetric private information retrieval (MM-SPIR) problem. Our scheme is a non-trivial generalization of the 2-party PSI scheme as it needs an intricate design of the shared common randomness. Interestingly, in terms of the download cost, our scheme does not incur any penalty due to the more stringent privacy constraints in the MP-PSI problem compared to the 2-party PSI problem.