Full Program »
Practical Over-Threshold Multi-Party Private Set Intersection
Over-Threshold Multi-Party Private Set Intersection (OT-MP-PSI) is the problem where several parties, each holding a set of elements, want to know which elements appear in at least
t
t sets, for a certain threshold
t
t, without revealing any information about elements that do not meet this threshold. This problem has many practical applications, but current solutions require a number of expensive operations exponential in
t
t and thus are impractical.
In this work we introduce two new OT-MP-PSI constructions using more efficient techniques. Our more refined scheme, which we call t-PSI, runs in three communication rounds. t-PSI achieves communication complexity that is linear in the number of parties, the number of elements they hold, and the intersection threshold. The computational cost of t-PSI is still exponential in
t
t, but it relies on cheap linear operations and thus it is still practical. We implement our new constructions to validate their practicality for varying thresholds, number of parties, and dataset size.