# Proof of correctness of an ElGamal encryption given a specific public key

Suppose Alice sends an ElGamal encryption of a value $$v$$ to Bob (using either the normal or exponential version of ElGamal). E.g. assuming publicly-known $$pk_{BOB} = h$$ and a generator $$g$$, Alice sends $$Enc(v,h) = (c_1,c_2) = (g^r, vh^r)$$ to Bob. Or for the exponential version, she sends $$Enc(v,h) = (c_1,c_2) = (g^r, g^vh^r)$$.

Assuming Alice is honest, Bob will be able to correctly decrypt and recover $$v$$. However, Alice might not perform the encryption correctly (intentionally or not). For example she could use some other public key $$h'$$ to encrypt $$v$$, and then Bob would decrypt to some value $$v'$$. As an example, suppose that the values are supposed to be representing an ASCII character, then the decrypted value $$v'$$ would be "garbage".

Security model: There is a third-party authority, where Alice must show that she is encrypting legitimate values.

Is there a way to amend the scheme such that either Alice can prove in Zero Knowledge (without revealing $$v$$) that she encrypted using $$h$$, or alternatively, Bob to prove in ZK (without revealing his secret key $$x$$) that decryption failed?

As you suggested, the most natural approach would be to use a zero-knowledge proof - namely, we can let Alice prove to Bob that she knows the plaintext encrypted in the ciphertext she sent, with respect to the public key $$h$$. However, this has an immediate issue: what prevent Alice from honestly encrypting some garbage, unrelated to the actual (say) ASCII character she knows? She can intuitively always do that - she could even always encrypt another valid-looking ciphertext, like, another ASCII character.
In all situations, an appropriate zero-knowledge proof should do the trick. Which one exactly depends on the exact scenario and variant of ElGamal: for example, using exponential ElGamal, Alice should not only prove that the knows $$(v,r)$$ such that the ciphertext is of the form $$(g^r, g^vh^r)$$: to prove that this can be decrypted, she must further prove that $$v$$ is "small" (smaller than some bound $$B$$ which is a parameter of the system). But without knowing your exact scenario, it is not possible to give a more precise answer for now. As a general principle: do not ask "how can Alice and Bob to this" when you think that this is what they should do in your scenario - instead, explain exactly what your scenario is, and what security property you wish to achieve exactly. Then we can figure out a solution.