Zero knowledge proof of possession of key Suppose Alice has at some point in time produced ciphertext $C$ from message $M$ with key $k$.
Suppose Alice has then passed $C$ to Bob, and also made a commitment to her key $k$ (thanks to nightcracker for this addition). 

Bob then stored it and passed it to a third party Dave, who also possesses $k$ and decrypts to get $M$, and based on $M$, performs certain operations. 

Assume that Dave has no contact with Alice and Bob.

Now Alice is incentivised to lie about the contents of $M$ to Bob.

Suppose at a later time that Alice provides Bob with the message $M$. Is there any sequence of actions that Alice can perform to prove to Bob that $M$ was the message she encrypted to give $C$, without handing over the key $k$?

Is there any connection with this: Zero knowledge password proof?
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.