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

Question

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?

Answer 1

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.

So, what exactly is your security model? Who should Alice and Bob prove something to (clearly, Bob is not the one Alice wants to sent a proof to: he has the secret key, so he can check by himself whether he got garbage or a valid-looking plaintext)? Do you assume some kind of authority that Alice and Bob interact with, to whom we can either ask Alice to prove that she encrypted the right value (is this right value known to the authority?), or ask Bob to prove that he could decrypt the ciphertext to a valid-looking value?

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.