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.

  • $\begingroup$ 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. $\endgroup$
    – SEJPM
    Mar 11, 2020 at 11:54
  • 1
    $\begingroup$ 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$. $\endgroup$
    – Sigmatics
    Mar 11, 2020 at 13:03
  • 1
    $\begingroup$ 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. $\endgroup$
    – SEJPM
    Mar 11, 2020 at 13:16
  • $\begingroup$ Thanks, I thinks this works well enough. I'll gladly accept it as an answer $\endgroup$
    – Sigmatics
    Mar 12, 2020 at 20:02

1 Answer 1


This would be possible by using textbook RSA, where the ciphertext is deterministic

You have the right idea there, that a deterministic scheme is the way to go. However note that every scheme is deterministic if you explicitly fix the randomness used.

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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.