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} $|)?
1 Answer
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:
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.
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.
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)
-
$\begingroup$ Thank you, that clears. Bloom filters , I just used as an example for a set with 0s and 1s; I was going through a paper on private record linkage and it uses encrypted bloom filters to calculate dice coefficient between the elements $\endgroup$ May 21, 2019 at 20:39
-
$\begingroup$ @mikero Do you happen to know if OPE has been implemented in any of the existing homomorphic encryption libraries? Thanks! $\endgroup$– SMDSep 28, 2019 at 2:51