# 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?

-
I changed A, B, C to Alice Dave and Bob and changed the text style of C and M to make the protocol and problem easier to read. –  orlp Sep 13 '13 at 13:25
I deleted my answer - you should add to your question that Alice commits to $k$. –  orlp Sep 13 '13 at 13:59
What's Dave's role in all this, from Alice and Bob's perspective? You say he "performs certain operations" based on $M$, but you also say that he has no contact with Alice or Bob (except, presumably, for receiving $C$ from Bob). So if Dave can't communicate the results of his "certain operations" back to Bob, why does he even need to be part of the whole system? –  Ilmari Karonen Sep 13 '13 at 14:16
Ps. An obvious solution would be for Alice to calculate a commitment $Q$ to $M$ and tack it onto $C$. Technically, this doesn't prove that $C$ decrypts to $M$, but it does prove that Alice knew $M$ when she generated $C$. –  Ilmari Karonen Sep 13 '13 at 14:53
To Ilmari Karonien: I don't know if Dave matters or not, I just thought I should include it in case. Alice proving that she knew $M$ in advance wouldn't help, unfortunately. –  Adam Sep 13 '13 at 15:05

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.
Thanks. I confess to being a neophyte in this area, so I will struggle to understand the details. But as may or may not have been obvious in the original description, I'm thinking about a symmetric encryption key $k$. What you're describing is using asymmetric encryption if I understood correctly. Does this change the answer (or can we somehow wrap the symmetric key with this asymmetric one?)? –  Adam Sep 13 '13 at 18:01
Because ElGamal is based on nice mathematics, the proofs in this case are nice. Proofs are possible for symmetric cryptosystems, but they will tend to be very complicated. You will also probably need a commitment to the key, so that Alice cannot cheat by decrypting $C$ to $M'$ using a different key. –  K.G. Sep 14 '13 at 11:16
Can you give any pointers as to where people have solved the problem with symmetric systems? I ask because earlier I had figured out for myself that it's possible when you have some kind of commutativity going on (e.g. $(a^b)^c = (a^c)^b$ type of thing), but symmetric systems don't have this property, right? –  Adam Sep 14 '13 at 12:33
One way is to construct a SAT problem for the decryption of C into M wich your key will satisfy, and use a zero knowledge proof for NP. One obstacle is that Alice might be able to find a different key $k'$ that decrypts $C$ to $M'$, but it is usually possible to find a solution to this. Getting a practical proof will probably take some work, but multi-party AES has been done, so why not? –  K.G. Sep 14 '13 at 16:03