1

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.

Sigmatics
  • 113
  • 4
  • 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
  • 1
    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
  • 1
    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

1 Answers1

2

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.

SEJPM
  • 45,967
  • 7
  • 99
  • 205