4
$\begingroup$

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.

Some additional information:

  • 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?

$\endgroup$
2
$\begingroup$

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)$
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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