# Scheme to verify AES key was correctly encrypted for public key recipient

In our file sharing scenario there are three participants: $$A$$, $$B$$ and $$C$$. Each participant has a public-private key pair (let's assume RSA for now). $$A$$ wants to share a symmetric AES key $$k$$ with the other participants. $$B$$ is given access to the file for free, while $$C$$ has to pay a fee for it. Thus, $$A$$ may potentially cheat $$C$$ by providing a wrong key $$k'$$, and $$B$$ should be able to act as an arbitrator in case of dispute.

The sequence is as follows:

• $$A$$ first shares the AES key $$k$$ with $$B$$ by encrypting it with $$B$$'s public key and makes it available to $$B$$. Now $$A$$ and $$B$$ have access to the symmetric AES key.

• Then, $$A$$ shares the same key $$k$$ with $$C$$ by encrypting it with $$C$$'s public key, making the ciphertext available to all participants.

• $$B$$ should now be able to prove that the ciphertext provided to $$C$$ is indeed the key $$k$$ encrypted with $$C$$'s public key.

This would be possible by using textbook RSA, where the ciphertext is deterministic. Since textbook RSA is insecure, this is not an option. I take it that this is similar to key escrow schemes/verifiable encryption, but I've been unable to figure out a scheme/crypto implementation for the proposed scenario.

• You could run a socialist millionaire's protocol between $B$ and $C$ so they can check whether they have the same $k$ without revealing it. – SEJPM Mar 11 '20 at 11:54
• This is a valid idea, but it doesn't prove whether $A$ misbehaved and sent the wrong key. $C$ can influence the outcome of the socialist millionaire protocol (i.e. to blame $A$ even though $A$ sent the correct key). Ideally, the scheme should be non-interactive ($B$ can prove that the ciphertext is correct/incorrect based on knowledge of $k$ and $C$'s public key) or interactive between verifier $B$ and prover $A$. – Sigmatics Mar 11 '20 at 13:03
• Suppose $c=\operatorname{Enc}_{\text{pk}_C}(k;r)$ is the ciphertext $A$ sends to $C$ using the randomness $r$. What stops you from having $A$ and $C$ send $c$ to $B$ and additionally have $A$ send $r$ to $B$ and then $B$ reproduces the now-deterministic encryption of $c$ using the known-good $k'$ $B$ has to check whether $c\stackrel{?}{=}\operatorname{Enc}_{\text{pk}_C}(k';r)$. If you're feeling fancy and don't want to just send over $r$ you could either encrypt it for $B$ or if you're feeling really fancy run a zero-knowledge proof of the above. – SEJPM Mar 11 '20 at 13:16
• Thanks, I thinks this works well enough. I'll gladly accept it as an answer – Sigmatics Mar 12 '20 at 20:02

So suppose you encrypt $$k$$ for $$C$$ as $$c=\operatorname{Enc}_{\text{pk}_C}(k;r)$$ using $$C$$'s public key and the randomness $$r$$. Now for the arbitration you give $$k$$ to $$B$$ who checks that the $$k$$ actually is the correct one. Then you have $$C$$ send the received $$c$$ (call it $$c_C$$) to $$B$$ and have $$A$$ send the sent $$c$$ (call it $$c_A$$) along with the randomness $$r$$ used for the encryption to $$B$$. You could possibly encrypt the randomness here using $$B$$'s public key. Then $$B$$ re-computes $$c'=\operatorname{Enc}_{\text{pk}_C}(k;r)$$ using the received randomness and its own known $$k$$ and checks whether $$c'$$ matches $$c_A$$ and $$c_B$$. If it matches at least $$c_B$$ then $$A$$ was honest (because then $$B$$ got the right key). If it only matches $$c_A$$ then either of $$A$$ or $$B$$ is lying but we don't know which, because $$B$$ could have produced its own ciphertext and sent it to $$B$$ or $$A$$ could have produced a correct ciphertext for $$B$$ but sent a bad one to $$C$$. I don't think there is a way to resolve this issue and find out who lied at the end.