The bloomfilter private set intersection (BPSI) is another naive and insecure protocol, but it is highly efficient and has lower communication cost than NPSI. It is based on bloomfilter [1], a probablistic data structure that uses k independent hash functions to compactly represent a set of n elements with only m bits. It supports O(1) set insertion and provides O(1) set membership queries at the cost of a small and tunable false positive rate. This means that we can know for certain an element is not in the bloomfilter, and we know an element is in the bloomfilter except with a small false positive probability.
In the protocol, the sender P1 inserts all its elements X into a bloomfilter, and sends it to the receiver P2. To compute the intersection, P2 needs to simply check the set membership of each of his elements Y with the received bloomfilter.
Sender (P1) Receiver (P2)
X Y
BF(X) ------------------------------> intersect(Y, BF(X))
BF(X): Bloomfilter bit set of inputs X
[1] Bloom, Burton H. "Space/time trade-offs in hash coding with allowable errors." Communications of the ACM 13.7 (1970): 422-426.