Take the 2-minute tour ×
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.

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

2 Answers 2

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

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.