How to prove that someone encrypted a specific (large) chunk of data

Question

Alice encrypts her data with HER secret key. Then she sends the encrypted data to Bob who should encrypt it with HIS secret key.

Caroline should then eventually get this double encrypted data. Caroline only wants to receive pseudo-random (looking) data which would only be decryptable for her if Alice and Bob BOTH tell her their secret key. She wants to be able to use this fact in court in case she and [Alice XOR Bob] get accused of deliberately saving and/or distributing intellectual property illegally. Caroline therefore wants to be sure that Bob really takes the encrypted data of Alice, encrypts it with HIS secret key and then sends it to her. How can that be achieved? Alice and Bob are allowed to use different encryption algorithms.

I suppose AES is not suitable for this task. I hope I was somehow able to express what I want in a comprehensible way. I know, my English is bad.

Answer 1

I may be interpreting your question incorrectly, but it sounds to me like you are asking if Caroline can prove (in court or whatever) that she can only gain access to some secret $S$ if both Alice and Bob collaborate in revealing it to her. Unfortunately as you have currently set up the question, I don't think that is possible, because your question establishes that Alice knows the secret $S$ before any encryption is applied (it's "her data", as you put it). Hence, it is always possible for Alice to simply tell Caroline $S$, regardless of whether Bob collaborates.

But, if we modify the set-up a bit, it is possible to prove what you want. We need to assume that neither Alice nor Bob knows $S$, and in addition we need a trusted third party and a secret sharing scheme. Only the trusted third party, Tim, starts off knowing $S$, and he can be trusted to a) not leak any information about $S$ to anyone at any point, and b) to reliably carry out the following three steps:

1. Tim generates a pad $P$ - a random string of bits equal to the length of $S$.
2. Tim establishes a secure channel with Alice (using e.g. secure public key exchange and PKI methods to prevent Man In the Middle attacks), and sends her the string $P \oplus S$.
3. Tim similarly establishes a different secure channel with Bob, and securely sends him $P$.

At this point, Tim has split the secret into two 'shares', and Alice and Bob only know what their own share looks like (i.e. random nonsense).

4. Alice and Bob then each encrypt their own share using authenticated encryption (e.g. AES-GCM) and their own secret keys.
5. Alice and Bob now send Caroline the encrypted shares.

This way, no one (aside from Tim) can know what $S$ is unless both Alice and Bob reveal their shares (e.g. by sharing their keys with Caroline). Knowing only one share gives you zero information about $S$ (besides the length), and as such if either Bob or Alice don't reveal their share then $S$ is safe.

As to any concerns about ensuring that Alice and Bob do their part (i.e. properly encrypt their shares) and don't simply forward their shares unencrypted to Caroline, I would note that simply forwarding the unencrypted shares to Caroline is equivalent to encrypting the shares but then revealing the keys to her -- so long as either Alice or Bob does their part properly Caroline cannot know $S$. It takes collaborative effort / incompetence by both Alice and Bob for $S$ to be revealed. If we cannot trust that at least one of the two will keep their key secret and properly run their part of the protocol then no scheme will succeed (so my scheme is not unique in that respect). But given my described scheme, one person doing their part properly is sufficient to keep Caroline provably in the dark.

Answer 2

Here's a simple solution, but with some proviso's that may or may not be acceptable...

Alice's private and public key: $skA$, $pkA$
Bob's private and public key: $skB$, $pkB$
Encryption is $E_x(P)$, where $x$ is the key, and $P$ is the plaintext.
Decryption is $D_x(C)$, where $x$ is the key, and $C$ is the ciphertext.

Summary of Protocol

1. $A \rightarrow C: E_{pkA}(E_{pkB}(S)) = e_1$
2. $C \rightarrow B: E_{pkB}(e_1) = e_2$
3. $B \rightarrow C: D_{skB}(e_2) = e_3$
4. $C:$ if $e_3 <> e_1 $ abort. Retry from step 2.
5. $C: purge(e_1,e_3) $

Explanation

1. Alice encrypts with Bob's public key, followed by her public key, and sends the encrypted data ($e_1$) to Caroline.

2. Caroline encrypts $e_1$ with Bob's public key, and sends the result ($e_2$) to Bob for decryption.

3. Bob decrypts $e_2$ and sends the result ($e_3$) back to Caroline.

4. Caroline can now check that Bob was able to decrypt $e_2$ using his secret key, by checking $e_1$ against $e_3$. If they are the same, it was Bob's public key, and she can continue otherwise she aborts and tries again.

5. Caroline then chucks away $ e_1 $ and $ e_3 $ and keeps $ e_2 $.

Discussion

• Alice could simply not encrypt using Bob's public key when computing $e_1$ but this situation is countered by Caroline ensuring that she keeps only $e_2$ and not $e_1$ or $e_3$.
• Bob cannot learn $S$ without Alice's secret key.
• Bob cannot cheat because his decryption of $e_2$ is checked against $e_1$.
• This solution requires 3 encryptions, not 2 as indicated in the question.
• Lawyers could always argue that $e_1$ was only ever encrypted with Alice's key (and Bob's key wasn't used), and that Caroline kept $e_1$ and then used Alice's corresponding key to decrypt $e_1$. This could be countered by using a third party machine to run the protocol on, the end result of which would be that Caroline takes away only $e_2$ on a usb stick, and the associated data is then securely purged.
• The end result, if the protocol is followed correctly, is that Caroline can be sure she has something that has at least been encrypted with Bob's public key. To ensure that it is also encrypted with Alice's key, she could run steps 2 and 3 with Alice as well as Bob, with their respective keys, but this would add another round encryption to the scheme. Unfortunately, she doesn't know what has been encrypted but what she does know is she does have something that was.

Answer 3

After having thought about this for a considerable amount of time I came up with the following as the easiest and best solution I could think of.

The following protocol assumes that Alice is trusted whereas Bob isn't.
$S_X(P)$ denotes signature by $X$ on $P$.
$E_X(P)$ denotes encryption using the public key of $X$ of message $P$.
$E_{K_X}(P)$ denotes symmetric AES-GCM encryption using the key $K_X$ of the message $P$.
$N_X$ denotes the $X$-th nonce which is used in combination with $E_{K_X}(P)$.

This is a three-way protocol that lets only Alice know the message.

1. $A\rightarrow B: N_1||E_{K_1}(m)$
2. $B\rightarrow A: E_A(K_2)||auth_B=S_B(E_A(K_2))||N_1||N_2||E_{K_2}(E_{K_1}(m))$
3. $A\rightarrow C: E_B(K_1)||auth_A=S_A(E_B(K_1))||E_A(K_2)||auth_B||N_1||N_2||E_{K_2}(E_{K_1}(m))$

Now the protocol actions:

1. Alice retrieves the message and encrypts using a random key $K_1$ which is stored (short-term). She finishes by sending the above message.
2. Bob generates a random key $K_2$ himself, which he uses to encrypt the provided message (by Alice). He then encrypts the symmetric key using Alice's public key and signs the resulting ciphertext. After this he sends the signature, the encrypted key and the resulting ciphertext.
3. Alice decrypts the provided ciphertext using the asymmetrically encrypted key and decrypts the resulting ciphertext using her symmetric key. She then checks that the $m$ value is correct. If this is the case she verifies $auth_B$ and if it's valid she calculates $E_B(K_1)$ and the signature $auth_A$. Alice deletes $K_1$ and $K_2$
4. Upon receivement Carol checks $auth_A$ and $auth_B$ and assumes correct treatment by trusting that Alice has validated Bob's encryption.

Note that $auth_A$ is neccessary to prove that Alice trusts the key.

Now only Alice and Bob together can decrypt the message $m$ as only Alice can decrypt $K_2$ and only Bob can decrypt $K_1$. Note further that AES-GCM uses CTR-mode internally resulting in the fact that $E_{K_2}(E_{K_1}(m))$ isn't vulnerable to meet-in-the-middle as this is basically $StreamPad_1 \oplus StreamPad_2 \oplus m$ and hence it's needed to have both keys to decrypt.

I hope this solves your problem.