  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, \cdots, M\}} \sum_{i \in \{1, \cdots
M\}\setminus {t}} \left\lceil \frac{|\mathcal{p}_t|N_i}{N_i-1}\right\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.
