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?

share|improve this question
    
Does my example describe your idea? I have an encrypted file having rows and columns. Now i want to give some party a key, which allows him to decrypt only certain columns of any row? – Olaf Jan 21 '16 at 13:47
    
…must be very fast in terms of computation time (<1ms) – Computation speed will strongly depend on the hardware you’re using! (Besides that, you should be aware of the fact that less than 1 millisecond is a goal that will be near to impossible to reach. Even if calling a function (the call itself, not it’s functionality) would take less than 1ms, fetching the to-be-encrypted data from disk/database is bound to take longer than t < 1ms.) – e-sushi Jan 21 '16 at 15:12
    
@Olaf: not completely, as a) there are no rows, my List is one-dimensional, b) the column approach would be equivalent to have a map (Index of the column and a value, where I just have IDs, their existence is already the only information that I need) – Fritz Jan 21 '16 at 19:35
    
@e-sushi: of course, I wanted to stress out that we need a fast implementation. Actually a simple method invocation does of course not cost 1ms, much less. As it's more a library which does everything in memory, there is no HDD access – Fritz Jan 21 '16 at 19:36
    
@Fritz Good to know. Thanks for info. (Not sure, but it may make sense to edit that into your question… incl. some hardware specs so users know what’s available to you. Like: Are dedicated AES CPUs available? Or crypto-ASICs of some kind? What hardware exactly is this going to run on?) – e-sushi Jan 21 '16 at 19:45

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)$
share|improve this answer
    
My implementation using HKDF and Blowfish seems to work fine anyway - implemented some time after the comment :) – Maarten Bodewes Jan 24 '16 at 16:40

sorry for reviving this thread, but the question is similar to my problem now.

however, mine is a 2D matrix with columns and rows, and when a party is given a key, he is able to decrypt certain columns.

can anyone advise?

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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