Scalable and secure Private Set intersection for big data
Changhee Hahn, Junbeom Hur · 2016
In this paper, we investigate Private Set Intersection (PSI) schemes that can be used to output intersection data between a client and a server in a way that only the client learns the output at the end of their joint computation. Recently, Dong et al. proposed a Bloom filter-based PSI scheme for big data. We show that a malicious client is able to learn not only the intersection but other part of the server's set in Dong et al.'s scheme. This can be delivered by submitting arbitrary Bloom filters as inputs. To this end, we suggest a Merkle tree-based countermeasure. It prevents malicious clients from learning any part of the servers set except the intersection. The security and performance analysis shows that our scheme is secure against the malicious client with a minor efficiency degradation.