how do we calculate set intersection using homomorphic encryption?

Question

I am new to this field. I want to learn how homomorphic encryption can be used for PSI. I am aware of other SMC protocols but I never understood how to use schemes like Paillier for PSI calculation. For example Alice and Bob have two bloom filters(with set cardinalities: |$ B_{Alice} $| and |$B_{Bob}$|they want to compare and see if they match. Alice sends the encrypted (encrypted using paillier) bloom filter to Bob along with the public key. Now, how does Bob build the Binary AND, i.e., how does he calculate E(|$ B_{Alice} $| $ \wedge $ | $ B_{Bob} $|)?

Answer 1

I'm not sure where Bloom filters necessarily come in. The "standard" way to use additively homomorphic encryption (that's what Paillier is) for set intersection is the oblivious polynomial evaluation (OPE) technique. It works like this:

1. Alice generates a polynomial whose roots are the items in her set: $p(x) = \prod_{a \in A} (x-a)$. She encrypts the coefficients of $p$ using an additively homomorphic scheme, under her own key. She sends the result $E_k(p)$ to Bob.

2. For each $b \in B$, Bob chooses a random value $r_b$ and uses the homomorphic property of the encryption scheme to evaluate $E_k\Big( r_b \cdot p(b) + b \Big)$. This requires only additive homomorphism since $b$ and $r_b$ are known to Bob. Note that: if $b \in A$ then $p(b) =0$ so the result is $E_k(b)$; otherwise the result is the encryption of a uniformly random value. Bob sends all of these ciphertexts back to Alice.

3. Alice decrypts the ciphertexts and computes the plaintext intersection with $A$.

This technique dates back to:

Efficient Private Matching and Set Intersection by Michael Freedman, Kobbi Nissim, Benny Pinkas (see Sec 4.1)