There are two parties who don't trust each other mutually, say A and B. A has a large set of strings. B has a string and needs to check if this is contained in A's set or not. B does not want to reveal the string to A and neither does A want to reveal all the strings in the set to B. But still, B should know the answer to her membership question from A.
Is there any existing encryption scheme that helps me do this. Please direct me in the right direction.
There is a simple and elegant solution with the additive variant of the ElGamal encryption scheme. I'll first describe the most naive version, and then discuss a bit some improvements.
First, A (who holds a database of size $N$ that is assumed to be over some group $\mathbb{Z}_p$) computes a degree $N$ polynomial whose $N$ roots are the elements of its database, in normal form. Think now of the $N+1$ coefficients $(a_0, \cdots, a_N)$ (in $\mathbb{Z}_p$) of this polynomial as the database stored by A.
B has an input $x \in \mathbb{Z}_p$. He sets up an ElGamal encryption scheme with message space $\mathbb{Z}_p$ (the message is encrypted in the exponent: $E(m;r) = (g^r, h^rg^m)$ where $(g,h)$ is the public key, and the secret key is $s$ such that $g^s = h$).
B computes encryptions $(c_1, \cdots, c_N)$ of $(x, x^2 \bmod p, \cdots, x^{N} \bmod p)$ and send them all to A. A can compute homomorphically from $(c_1, \cdots, c_N)$ an encryption of $a_0 + \sum_{i=1}^N a_i x^i \bmod p$. The latter is either $0$ (if x is in A's database) or some other value. A picks a random element $r$ from $\mathbb{Z}_p$ and homomorphically multiply this encryption by $r$. He sends back an encryption of $r(a_0 + \sum_{i=1}^N a_i x^i) \bmod p$ to B. The latter checks whether this encrypts $0$ or not (no need for efficient decryption, so the use of the additive ElGamal is not a problem here). If it's 0, his element is in A's database, otherwise it is'nt.
The problem of this method is that it requires sending $N$ ciphertext, which can be large. A slightly more involved solution is to let B send instead encryptions of $(x^1, \cdots, x^{\sqrt{N}})$ and of $(x^{\sqrt{N}}, x^{2\sqrt{N}}, \cdots, x^{N})$, a total of $2\sqrt{N}$ ciphertexts. The server now computes the coefficients of the degree $N$ polynomial whose roots are the elements of his database, written in the following form: $P(X) = \sum_{i = 1}^{\sqrt{N}} F_i(X)\cdot X^{i{\sqrt{N}}}$, where each $F_i(X)$ is a degree-${\sqrt{N}}$ polynomial with coefficients $(a_{ij})_j$. From the ciphertexts sent by B, A can homomorphically compute encryptions of $F_i(x)$ for each $i$. Then, he generates ${\sqrt{N}}$ random masks $r_i$, and returns encryptions of $F_i(x) + r_i$ together with an encryption of $\sum_i r_i X^{i{\sqrt{N}}}$, homomorphically computed from the ciphertexts he revealed from Bob.
From the $F_i(x) + r_i$ and $\sum_i r_i X^{i{\sqrt{N}}}$, Bob can recover $P(x)$, and nothing more (this can be formally proven). The total communication was reduced to $3\sqrt{N}+1$ ciphertexts. However, I think one must now have efficient decryption for this to work, hence another scheme (e.g. the Paillier scheme) must be used.
If the encryption scheme allows to perform one multiplication in addition to many sums (there are simple schemes doing that under the LWE assumption), then this can be reduced to $O(N^{1/3})$.
I know that considerably more involved techniques allow to reduce that to as small as $O(\log N)$, but I think they are just theoretical works, not really practically relevant as of today. I do not claim that any of the solutions I discussed is the optimal one it terms of practical efficiency, I do not have a detailed knowledge of a state of the art. They are just simple solutions that come to my mind.
