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".


3 Answers 3


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.

  • 1
    $\begingroup$ You are right, @user7863, I corrected the random numbers. However, could you explain how the protocol works from my example? $\endgroup$ Aug 2, 2013 at 13:47

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:

Part 1 of description

Part 2 of description

  • 2
    $\begingroup$ The explanation from the paper is a good one, but once this picture is not available any more, the answer lacks its main point. It is advisable to copy text and not just upload a picture somewhere, which will be unavailable at some point in the future. $\endgroup$
    – tylo
    Feb 26, 2015 at 13:49

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.


Your Answer

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

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