Zero knowledge proof of possession of key
Alice can prove that the decryption of $C$ is $M$. This can be done using zero knowledge proofs.

Simple example: Suppose $C = (x,w)$ is an ElGamal encryption of $M$ under public key $y$, that is $(x,w) = (g^r, y^r M)$ for some $r$. Suppose that the decryption key is $a$, that is, $y=g^a$. Then we know that $M = wx^{-a}$, or $x^a = w/M$. That is, the logarithm of $w/M$ to the base $x$ is the same as the logarithm of $y$ to the base $g$.  Conversely, if the logarithms are equal, the decryption of $C$ is $M$.

Now Alice can prove that the decryption of $C$ is $M$ by proving the equality of the two discrete logarithms. There are standard zero knowledge proofs for this.