Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question

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.

share|improve this answer
You are right, @user7863, I corrected the random numbers. However, could you explain how the protocol works from my example? – Bernardo Pacheco Aug 2 '13 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

share|improve this answer
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. – tylo Feb 26 '15 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.

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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