Annual Computer Security Applications Conference (ACSAC) 2020

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.

Rasoul Akhavan Mahdavi
University of Waterloo

Thomas Humphries
University of Waterloo

Bailey Kacsmar
University of Waterloo

Simeon Krastnikov
University of Waterloo

Nils Lukas
University of Waterloo

John Abraham Premkumar
University of Waterloo

Masoumeh Shafieinejad
University of Waterloo

Simon Oya
University of Waterloo

Florian Kerschbaum
University of Waterloo

Erik-Oliver Blass

Paper (ACM DL)




Powered by OpenConf®
Copyright©2002-2021 Zakon Group LLC