4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ What you're looking for is called Private Information Retrieval (PIR) and usually doesn't scale well. $\endgroup$ – SEJPM Oct 25 '16 at 20:34
  • $\begingroup$ @SEJPM I dont thing this actually PIR. In PIR a server is hold all the data and a client wants to retrieve a data item without letting the server know which item is being retrieved. A (non-efficient solution) to PIR would be for the server to send the entire database to the client. This would clearly NOT be acceptable in this scenario. $\endgroup$ – Guut Boy Oct 25 '16 at 21:05
  • $\begingroup$ I think the problem you are interested in is called Private Set Inclusion or sometimes Private Membership Test. I do not know of any encryption scheme that directly helps solve these problems. But this paper by Pinkas et al. usenix.org/system/files/conference/usenixsecurity14/…, describes a protocol using Oblivious Transfer in the context of Private Set Intersection. It may be worth looking into. $\endgroup$ – Guut Boy Oct 25 '16 at 21:17
  • $\begingroup$ An accumulator implemented with RSA could be a solution; group signature scheme could be a reference. crypto.stackexchange.com/questions/31102/… would be relevant here. $\endgroup$ – Vadym Fedyukovych Oct 26 '16 at 9:26
4
$\begingroup$

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.

| improve this answer | |
$\endgroup$
  • $\begingroup$ Do you have a name for this method ? I would like to find more information about it, and maybe some numerical examples, or code. Thanks. $\endgroup$ – Jd Bertron Feb 13 '18 at 18:24
  • $\begingroup$ The generic setting is that of private set intersection (PSI). The first solution I described is the seminal paper in this area, ie this one. The second solution is mine (in the sense that it was not written anywhere in the literature, but uses standard techniques and can probably be deemed "folklore"). You can find papers about PSI on the ePrint archive. Latest work use more advanced techniques such as Cuckoo hashing and Bloom filters (look at the dblp page of Benny Pinkas, it should be a good starting point). $\endgroup$ – Geoffroy Couteau Feb 13 '18 at 22:27
  • $\begingroup$ In this specific scenario, you do not want just PSI, you want PSI for sets of unequal size (set membership testing being a extreme version of it). Some works have focused on this aspect, see e.g. this paper, and references therein, or this paper. $\endgroup$ – Geoffroy Couteau Feb 13 '18 at 22:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.