Verification of encryption for ElGamal cryptosystem

Question

Suppose Alice wants to convince Bob that ciphertext c = (a, b) = (g^r, m*h^r) is some properly encrypted plaintext (not just random numbers). Obviously she can use zk-proof of discrete logarithm knowledge for the first part of the ciphertext (a = g^r). But what can she do with b-part?

One of my ideas: if m belongs to subgroup G (with a generator g) than we should prove that b belongs to G. But it's just a new problem.

Alice can also use exponential ElGamal (c = (g^r, g^m * h^r)) if it makes things easier.

Answer 1

Actually, an ElGamal ciphertext $(a,b)$ is "valid" iff $(a,b) \in G^2$, because for any message $m\in G$ and any $\mathsf{pk}\in G$, the encryption of $m$ will be in $G^2$, because for any $r$, $(g^r,\mathsf{pk}^r\cdot m)\in G^2$, and any $(a,b)$ chosen in $G^2$ can be correctly decrypted by any secret key by computing $m=\frac{b}{a^\mathsf{sk}}$. The proof of knowledge of the random coin $r$ is sufficient to show that you know how the ciphertext was produced.

I do not know if that answers your problem.