Suppose for $sk = x$, $pk = g^x$ we encrypt message $m$ with ElGamal encryption as $(g^r,m\cdot pk^r)$. My goal is to prove that I performed the encryption correctly, i.e. that the same $r$ is used across $g^r$ and $m\cdot pk^r$.

I thought of a simple $\Sigma$-protocol to show this as follows:

  1. Prover samples $q_1,q_2$, computes $R_1 = q_1\cdot pk^{q_2}$ and $R_2 = g^{q_2}$ and sends $R_1, R_2$ to Verifier.
  2. Verifier sends random challenge $e$ to prover.
  3. Prover computes $z_1 = q_1 \cdot m^e$ and $z_2 = q_2 + e\cdot r$. Sends $z_1$ and $z_2$ to verifier.
  4. Verifier checks if $R_1 \cdot (m \cdot pk^r)^e= z_1 \cdot pk^{z_2}$ and $R_2 \cdot (g^r)^e = g^{z_2}$

By pen and paper the math checks out but I'm not sure if I miss something? (this question is a follow-up on an older related question of mine: Proof of correctness of an ElGamal encryption given a specific public key). For example, is there a chance that $z_1$ in practice could leak information about the message $m$?


1 Answer 1


The proof doesn't work (even if you fix it up by having the prover initially send $R_1, R_2$, rather than $q_1, q_2$, which you likely intended); the holder of the private key can generate a valid looking proof, even if the ciphertext doesn't actually decrypt to the plaintext.

Suppose the prover has a public key $pk$ (and the corresponding private key); he has has a message $M'$ that bears no relation to the ciphertext $C$. Then, here is how he can generate a 'proof':

  • Steps 1, 2 proceeds as specified

  • In step 3, he computes $z_2 = q_2 + e \cdot r$ (as specified), however he computes $z_1 = R_1 \cdot C^e \cdot pk^{-z_2}$

  • In step 4, the verifier will note that both relations hold.

(That the verifier never uses the value of the supposed plaintext that the proof is supposed to be about should be enough to show that something is missing here...)

  • $\begingroup$ Thanks fixed the $R_1, R_2$. So my initial goal was to show that the prover used the same randomness $r$ for the two ElGamal ciphertexts. Would this proof prevent the prover from sending something like $(g^r, m \cdot pk^{r'}$ and $r \neq r'$? $\endgroup$
    – Panos
    Apr 29, 2022 at 22:22
  • $\begingroup$ @Panos Is $m$ supposed to be known to verifier. If not the statement is trivial: an $m$ always exist, and it actually is the proof of knowledge of $m$ by someone who does not hold the private key. In that case this looks OK, (I haven't seen the original version): an honest verifier simulator and extractor both exist. Otherwise, sigma protocol for DDH tuples are available, maybe you can use that. $\endgroup$ Apr 30, 2022 at 3:12

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.