Suppose we have two sets of ElGamal cipher texts encrypted with the same public key $y$ in a prime order group:

$C_i = (g^{r_i}, a_i y^{r_i}) $ for $ i \in \{1 ... n\}$


$D_j = (g^{s_j}, b_j y^{s_i}) $ for $ j \in \{1 ... m\}$

Bob own the private key $x$ to $y$ such that $g^x = y$

Alice wants to know if there is any intersection between the two sets of plaintexts $ \{a_1,... a_n\}$ and $ \{b_1,... b_m\}$ , i.e. if there exists $i, j$ such that $a_i = b_j$, but without revealing to either alice or bob any other information about the two sets or their individual elements.

One way to do this is by performing an oblivious test of plaintext equality for every pair of $C_i, D_j$. This requires $O(m*n)$ exponentiations in the blinding phase. I want to propose a protocol that only requres $O(m + n)$ exponentiations in the blinding phase.

My question is, would the following protocol work? Is it safe/unsafe and does it leak any information?


Alice samples a random $S$ from $\mathbb{Z}_q$ and exponentiates (aka blinds) each ciphertext from both sets:

$(g^{r_iS}, a_i^S y^{r_iS}) $


$(g^{s_jS}, b_j^S y^{s_iS}) $.

Alice then computes every division of pairs of ciphertexts from the sets:

$(g^{s_jS - r_iS}, b_j^S a_i^{-S} y^{s_jS - r_iS}) $

and the rest of protocol proceeds as a Chaum-Pederson protocol for each pair of elements.

So essentially, the instead of doing a division for every pair of ciphertexts and then blinding the encrypted quotient, we first blind each ciphertext with the same blinding factor ($S$) and then perform all the divisions.



Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.