# Verification of encryption for ElGamal cryptosystem

Suppose Alice wants to convince Bob that ciphertext c = (a, b) = (gr, m*hr) 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 = gr). 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 = (gr, gm * hr)) if it makes things easier.

• One can use the same response for $r$ (part of the proof) for two proofs about both parts of the ciphertext. "Some $r$ exists" seems somewhat general; practical cases may include something like "and $m$ is either $g$ or $1$" (0 or 1 for the second variant). Will you refine your "properly" condition? – Vadym Fedyukovych Nov 17 '18 at 16:13

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.