How does an oblivious test of plaintext equality work?

Question

Assume an ElGamal Cryptosystem. Assume a set of three players, $P_1$, $P_2$ and $P_3$. The private key $x$ is shared among the players. The player $P_1$ has a piece of the private key $x_1$, $P_2$ has the piece $x_2$ and $P_3$ has $x_3$.

Assume the following messages, $m_1$ and $m_2$.

Let $E(m_1)$ and $E(m_2)$ be two ElGamal ciphertexts.

The elements $r_1$ and $r_2$ are random numbers, and $y = g ^ x$, where $g$ is a generator of the group.

Encrypted message m1: $E(m_1) = (g ^ {r_{1}}, m_1 \cdot y ^ {r_{1}}) = (a_1, b_1)$

Encrypted message m2: $E (m_2) = (g ^ {r_{2}}, m_2 \cdot y ^ {r_{2}}) = (a_2, b_2)$

The question is: how can the holders (players) of the private key execute the oblivious test of plaintext equality proposed by Schnorr and Jakobsson? Specifically, how can the three players can determine if $m_1 = m_2$ without revealing the messages?

PS: The protocol oblivious test of plaintext equality proposed by Schnorr and Jakobsson is in the article entitled "Efficient Oblivious Proofs of Correct Exponentiation".

Answer 1

You've messed up your question. Since the two ciphertexts both use the same r, anyone can easily check if $m_1=m_2$. This is not the interesting case.

But if the two ciphertexts are $(a_1, b_1) = (g^{r_1}, m_1 y^{r_1})$ and $(a_2, b_2) = (g^{r_2}, m_2 y^{r_2})$, then the tuple $(g, y, a_1/a_2, b_1/b_2)$ is of the form the mentioned paper deals with.

Answer 2

The following describes a PET protocol, based on Mix-and-Match secure multiparty computation procedures [Jakobsson / Juels 2000].

In addition, consider that the operations for discrete exponentiation (as required for blinding and decrypting) are executed in a treshold crypto sense, i.e. every player produces his partial blindning / decryption result, which then has to be combined.

Here we go:

Answer 3

I just tried to write down a very short answer, but I noticed that you actually can't do that with the current situation:

It is not clear, who knows $r_1$ and $r_2$. This is important, because otherwise you can not prove that the ciphertexts are equal.

What you would have to do is to compute the encryption of $(m_1/m_2)^{r_3}$ with a random $r_3$, and then you have to prove that it is encryption of $1$. However, without knowing $(r_1/r_2)$, you simply can not do that.

Knowing the secret key does not help to extract $r_1$ from $g^{r_1}$ or from $h^{r_1}$. You would still have to calculate a discrete logarithm.