Efficient Multiparty Probabilistic Threshold Private Set Intersection

Abstract

Threshold private set intersection (TPSI) allows multiple parties to learn the intersection of their input sets only if the size of the intersection is greater than a certain threshold. This task has been demonstrated useful with practical applications, and thus many active research has been conducted. However, current solutions for TPSI are still slow for large input sets e.g., n=2^20 for the set size, and the potentially practical candidates are only secure against semi-honest adversaries. For the basic PSI, there have been efficient and scalable solutions, even in the malicious settings. It is interesting to determine whether adding a threshold feature would inherently incur a large overhead to PSI.