2 Part Encryption

Question

Can anyone tell me if an encryption / decryption scheme like the following exists?

Encrypted1 = SomeCryptoFunction(Data, Key1)

Encrypted2 = SomeAdditionalCryptoFunction(Encrypted1, Key2)

Data = SomeDecryptFunction(Encrypted1, Key1)

Data = SomeDecryptFunction(Encrypted2, Key2)

In words, the idea is follows.

1. Provider encrypts data (In a general fashion, using Key1)
2. User requests encrypted (With Key1) data
3. User runs additional encryption process to provide data decryptable by user key (Key2).
4. User decrypts with their key (Key2).

Note: I am looking for this overall process, it does not have to be exactly the same, just the general idea.

Does this exist, or have I got a case of wishful thinking?

Edit (For clarity after seeing the comments)

The idea for application is as follows:

1. A company shares media encrypted with their key (Key1) over p2p.
2. The companies users share the encrypted media between themselves.
3. A user wishes to access the information.
4. It is undesirable to have everyone share a common key, so The idea is to give each user a small routine to run on the already encrypted data, and a key to decrypt it with. Each routine and key combination would be "unique".
5. The user fetches the key and routine from the company server
6. Run's the routine on the data
7. And decrypts with their own key

Answer 1

As SEPJM suggests in the comments, this could be done with Proxy Re-Encryption (PRE). Proxy Re-Encryption is a type of public-key encryption where ciphertexts encrypted under the public key of user $A$ can be transformed (i.e., re-encrypted) into ciphertext decryptable by the private key of user $B$; the re-encryption process does not reveal any information about the underlying message, so it can be performed by a separate entity (i.e., the proxy). In order to re-encrypt ciphertexts, user $A$ has to create first a re-encrytion key that makes this process possible, and gives this key to the proxy.

The application of PRE to your problem could be as follows: Since this is a type of PKE scheme, everyone has a pair of public and private keys: user $U_i$ has keys $(pk_{U_i}, sk_{U_i})$, and the company $(pk_C, sk_C)$.

Suppose that files are initially encrypted under the company's public key $pk_C$. For example: $Encrypted_{C,1} = Enc(pk_C, file_1)$

The company creates a re-encryption key for each user ($rk_{C\to U_i}$) and gives this key to the company server, which acts as a proxy.

Users now only have to request the re-encryption of encrypted files. For example, suppose that user $U_i$ requests the re-encryption of $Encrypted_{C,j}$. The proxy uses $rk_{C\to U_i}$ to transform $Encrypted_{C,j}$ into $Encrypted_{U_i,j}$. Now user $U_i$ can decrypt this with $sk_{U_i}$

Answer 2

A variant of ElGamal encryption would do. That is, let $g$ be a generator of a multiplicative group, $PKey_1 = g^{Key_1}$ be public key of the first party and $PKey_2 = g^{Key_2}$ of the second party, $(r_1, r_2)$ be random ring elements. Let $Data$ be represented by a group element. Then $$Encrypted_1 = (g^{r_1}, Data (PKey_1)^{r_1})$$ $$Encrypted_2 = (g^{r_1}, g^{r_2}, (Data (PKey_1)^{r_1}) (PKey_2)^{r_2})$$

Answer 3

It seems to me that simple layered encryption scheme should satisfy your requirements:

1. For each data file $m$, the distributor (Alice) generates a random symmetric encryption (e.g. AES) key $K_m$, and encrypts the data with it to obtain the ciphertext $C_m = E(m, K_m)$.

2. For each receiver $1 \le i \le n$, Alice encrypts the random key $K_m$ with the $i$-th receiver's (public) key $K_i$ to obtain the encrypted key $C_i = E(K_m, K_i)$.

3. Alice joins the encrypted keys and data together as $C = (C_m; C_1, \dots, C_n)$, using some suitable data serialization scheme, and distributes the result.

4. To decrypt the data, the receiver (Bob) locates their own encrypted key $C_i$ in the distributed message $C$, decrypts it using their private key $K_i$ to obtain the per-file encryption key $K_m$, and then uses that to decrypt $C_m$ and so obtain the original data $m$.

Alternatively, Alice can store the per-file key $K_m$, distribute only $C_m$, and generate and supply the encrypted key $C_i$ to each receiver $i$ only upon request. This somewhat reduces the amount of data that needs to be distributed among all the receivers, and also provides some additional flexibility. (E.g. Alice does not need to know all the recipients when she generates and distributes the ciphertext.) Of course, this requires the recipients to have some way of contacting Alice and requesting the keys.

Conveniently, you may not even need to implement this scheme yourself, since this is actually standard use case for public-key encryption. Any standard crypto toolkit, such as PGP / GnuPG, should support encrypting a message to multiple recipients using essentially the method described above. (Generating the per-user keys on demand is, alas, not supported out of the box, although there are workarounds to achieve effectively the same result.)

Note that this scheme does not provide any sort of "traitor tracing" features (which belong to the domain of steganography rather than cryptography, anyway); anyone who gains access to the message key $K_m$ can share it with anyone they like, with no way to trace who leaked it. However, anyone with access to $K_m$ and $C$ could also just decrypt the data $m$ and share that, so in that sense the ability to share $K_m$ does not add any new vulnerabilities to the scheme that would not exist in any similar system anyway. If you wished to detect such leaks, you'd have to somehow arrange for every recipient to somehow obtain a different version of the data $m$, which would be significantly harder (particularly as you'd no longer be able to treat the data as a "black box", but would have to actually tailor your cryptosystem to the specific data format and type of content you're distributing).