Efficient Threshold Private Set Intersection

Abstract

Threshold private set intersection (TPSI) allows a receiver to obtain the intersection when the cardinality of the intersection is greater or equal to the threshold, which has a wide range of applications such as fingerprint matching, online dating and ridesharing. Existing TPSI protocols are inefficient because almost all of them rely on lots of expensive public-key techniques or require an exponential number of possible combinations among the shares. In this work, we design an efficient TPSI protocol, which achieves computational security in semi-honest model. To improve the efficiency of the TPSI protocol, we design a new TPSI protocol based on garbled Bloom filter (GBF) and threshold secret sharing, which uses a small amount of public-key operations. Moreover, our protocol combines with the Reed-Solomon decoding algorithm to reconstruct the secret which is a feasible method to avoid calculating all possible combinations among the shares. The performance analysis shows that our protocol is more efficient than the previous TPSI protocols. To the best of our knowledge, the optimal TPSI protocol implemented by Zhao and Chow (WPES'18) has an online time of 78 seconds to compute the intersection of two datasets of 100 elements each with threshold t = 50. In contrast, our protocol has a total time of 2.988 seconds.

Keywords

• Garbled bloom filter
• secure multiparty computation
• threshold private set intersection
• threshold secret sharing