Practical Over-Threshold Multi-Party Private Set Intersection

Practical Over-Threshold Multi-Party Private Set Intersection

연구 분야: Cryptography

학회: ACSAC '20: Proceedings of the 36th Annual Computer Security Applications Conference

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 sets, for a certain threshold 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 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, runs in three communication rounds. 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 is still exponential in 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.