# Full encryption of IDs, partial decryption with customer specific key

I am looking for a "partial" encryption/decryption algorithm.

Let's say I am encrypting the following List of IDs (long values) $[1,2,3,4]$ (with a secret key) to an encrypted string $e$, I would like to produce several keys $k_1,k_2,...,k_n$, which can decrypt just a subset (some IDs).

For example:

val rawIds = [1,2,3,4,8]                         # Array of Long
val e = encrypt(rawIds, secretKey)               # An encrypted String

decrypt(k1, e) = [1]                             # Decryption of e with key k1
decrypt(k2, e) = [2,3]                           # Decryption of e with key k2

Both the encryption and decryption must be very fast in terms of computation time (<1ms). We want to produce keys, which can decrypt the value $e$ in way that only a subset of IDs can be decrypted.

$k_1$ for example is able to decrypt $e$ (but only retrieves $ID_1$) where $k_2$ can decrypt the same encrypted value but retrieves $ID_2$ and $ID_3$. He might even get $ID_5$, but this was not in the raw string.

When creating the keys, we could add the IDs which can be extracted somehow to the decryption key.

Update:

The possible values of the IDs are known, there is a predefined set (let's call them $ID_1,ID_2,...,ID_n$).

The business purpose is the following:

• I have 2 customers, where I know that customer1 is only allowed to see $ID_1$, therefore I create a key $k_1$ (and add the meta information $ID_1$).
• The second customer is allowed to see $ID_2$, $ID_3$ and $ID_5$ (therefore I create a special key $k_2$ for him).
• Both customers will get the same encrypted value e, and both can decrypt it but will get back a list of IDs, where every element is allowed to be extracted by that customer).

This was meant by: I add the IDs to the decryption key.

• It's only one entity which is encrypting, don't need to decrypt with the secret key
• No need to check authenticity of the encrypted value (always trust)
• When creating keys, the actual IDs (Long values) which can be extracted can be added to the actual key.

Where to start? Has anybody an idea of a similar existing approach?

So lets assume a few things:

1. just symmetric primitives suffice;
2. a symmetric key derivation function and single block encrypt with a 64 bit block cipher is sufficiently fast;
3. the ID's are unique and not related to customers;
4. we're not afraid of customers sharing ID's;
5. there is protection against customers simply guessing ID's;

Scheme:

• establish a master key $k_m$
• derive customer keys and distribute to customers: $k_{c,name} = KDF(k_m, name)$
• derive a data key for each ID with index $i$: $k_{id, i} = KDF(k_m, i)$
• create and distribute the encrypted array where each entry $C_i = E(k_{id, i}, ID_i)$

Now comes the tricky part:

• when a customer wants to get the ID's he sends you the set of indices to the ID's;
• you calculate the customer key and a customer specific data key for each entry: $k_{c,name} = KDF(k_m, name)$ and $k_{c,name,i} = KDF(k_{c,name}, i)$
• you calculate the difference between the data key and customer specific data key for each entry: $k_{x,i} = XOR(k_{c,name,i}, k_{id, i})$
• you send a map consisting of elements $(i, k_{x, i})$ back to the customer
• the customer can now perform $k_{id,i} = XOR(k_{c,name,i}, k_{x, i})$ for each entry
• and of course calculate $ID_i = D(k_{id, i}, C_i)$