All Dates/Times are Australian Eastern Standard Time (AEST)

Technical Program

Paper Detail

Paper IDD3-S2-T4.1
Paper Title An Information-Theoretic Scheme for Multi-Party Private Set Intersection
Authors Zhusheng Wang, University of Maryland- College Park, United States; Karim Banawan, Alexandria University, Egypt; Sennur Ulukus, University of Maryland- College Park, United States
Session D3-S2-T4: Multi-Party Computation I
Chaired Session: Wednesday, 14 July, 22:20 - 22:40
Engagement Session: Wednesday, 14 July, 22:40 - 23:00
Abstract We investigate the problem of multi-party private set intersection (MP-PSI). In MP-PSI, there are $M$ parties, each storing a data set $\cp_i$ over $N_i$ replicated and non-colluding databases, and we want to calculate the intersection of the data sets $\cap_{i=1}^M \cp_i$ without leaking any information beyond the set intersection to any of the parties. For a specific communication protocol, we propose an information-theoretic scheme for MP-PSI based 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, 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.