What cryptographic protocol or algorithm I can use to encrypt/decrypt a subset of columns of a database table for each user?

What cryptographic protocol or algorithm I can use to encrypt/decrypt a subset of columns of a database table for each user?

For example say I have a database table with 50 columns

col1, col2, col3, col4......col50


Now I want to reveal the data such that

user1 can see (have access to) col15 and col17 only  at time t1 and
user2 can see (have access to) col7, col9 and col20 only  at time t1
user3 and user4 can both see data only in col40 at time t1.
user1 can see (have access to) col24 only (which means access to previously assigned col15 and col17 will be disabled) at time t2


I am thinking if I can issue tokens to users such that each token would hold access to set of columns in a database table or something like that.

What kind of efficient protocol or algorithm I can use to construct such scheme ?

My scalability requirements

At most I will have is probably 1000 columns (maximum) I can have millions or billions of users. Algorithms than can scale for millions is also ok

• It seems you have time slots where access can change. This might quickly make any kind of cryptographic solution inefficient/slow for your purposes. If user1 loses access at t2 to some columns, do you want the cryptographic scheme to enforce this change (like DRM) or do you want to enforce it legally? The currently given answer doesn't cover this. – Artjom B. Jan 13 '18 at 18:25

A solution using attribute-based encryption

You could solve the problem you pose relatively elegant using attribute-based encryption (ABE; cf. [1]). For example, using a ciphertext-policy ABE you could do the following. Let {col1, col2, ..., col50} be the universe of attributes and, for each user, assign a key with respect to the attributes she is allowed to access. To take your example user1 would get a key with respect to {col15, col17}. Each column is then encrypted with respect to its column attribute so that every user who is in possession of a key with the respective attribute can decrypt the column.

An alternative solution

Since it seems that the number of columns you want to encrypt is rather small you could also use an alternative approach known as hybrid encryption: you choose a symmetric encryption scheme and encrypt each column under a separate key. Additionally you use an asymmetric encryption scheme which is used to encrypt the respective symmetric keys for the users who have access to a certain column. Let $k_1, \dots, k_{50}$ be the symmetric keys used to encrypt column 1 to column 50, then - again taking your example - you would encrypt $k_{15}$ and $k_{17}$ under the public encryption key for the asymmetric encryption scheme of user 1.

Scalability requirements

Since the number of columns is relatively small (< 1000), I think that both solutions above should perform well. Note that for the second solution the size of the ciphertexts which are handed to the users are of linear size in the number of columns. Using the ABE approach you will be able to get constant size ciphertexts (depending on the used ABE), but this will come at the cost of more expensive encryption and decryption. So choosing one of those two approaches can be viewed as choosing a trade off between ciphertext size and efficiency.

References

• Hi dade, Thank you so much for that response. I am new to cryptography..and I will read through ABE. but based on your answer I felt like I had to add more information to my question and therefore i did. can you please take a look now ? – user1870400 Jan 4 '18 at 13:52
• Hi @user1870400, yes of course! I will update my answer according to your updated question. – dade Jan 4 '18 at 13:56
• Thanks dade. What are some of the ABE's I can use or you suggest in this case? Any simple examples you can point me to ? That will be a great help since I am a novice in cryptography.. – user1870400 Jan 4 '18 at 14:13
• The first CP-ABE was "John Bethencourt, Amit Sahai, Brent Waters: Ciphertext-Policy Attribute-Based Encryption. IEEE Symposium on Security and Privacy 2007: 321-334". I think this should be relatively easy to understand and - due to the simplicity of your policy - already give you constant size ciphertexts. For more illustrative descriptions I would look for introductory lecture notes or slides on ABE. – dade Jan 4 '18 at 14:49
• Hi dade. you said the following.."Let {col1, col2, ..., col50} be the universe of attributes and, for each user, assign a key with respect to the attributes she is allowed to access". I have to design something such that I should allow a user to access any subset of {col1, col2, ..., col50} so this means I need to create 2^n keys (power set) and if I have 50 columns it will be 2^50 keys and if I have 1000 columns it will be 2^1000 keys. Thats a lot of keys right. I am wondering how that is efficent or if there is any better way? – user1870400 Jan 5 '18 at 9:45