Zero Knowledge proof of correct ElGamal encryption

Question

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$?

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