What encryption/decryption method should I use when multiple users should have access to the encrypted information?

Question

Ok, I am in a little bit of cryptographical fix :D

I need to figure out a way to encrypt and decrypt data handled by a website. The website is intended only for a certain group of people who will use it to upload and search sensitive information.

Data is entered by them using a browser, which should be encrypted before sending and storing it in the server/database.

On the other hand when these users search for a value (say, account number) in the database, it is queried whether present in the database and if yes, it is decrypted and displayed on the browser.

The whole point of encryption/decryption is to make sure that website hosters, owners and administrators do not understand the data values.

It is a website that has multiple users who might be accessing the same data/values from the same database. If we have 1000 registered users, the information uploaded by each of them should be available to all of the 1000 users.

The problem here is that this is not a person to person encryption/decryption (like sending an encrypted email), therefore I am not sure if the private and public key cryptography can be implemented in it's raw form. What is the logical way to implement cryptography in this situation?

Answer 1

Here's an example scheme that should work with $\mathcal O(r)$ operations for $r$ registrations and $\mathcal O(n+r)$ operations for $n$ documents and $r$ revoked (simultaneously) user accounts, but of course would perform all (eg search) operations client-side. This also involves only $\mathcal O(n+r)$ keys. Doing something like this (securely, partially) server-side is possible but more complex, this is called searchable or structured encryption and allows you to eg search for specific keywords / tags without the server learning the precise keyswords. This is eg deployed by pixek (RWC 2018 slides PDF) where apparently these three schemes are used: One, Two, Three.

The initial setup goes like this:

• Define a (random) symmetric key $K$ for the entire database.
• Define a (random) symmetric key $K_i$ for the $i$-th document.
• Encrypt the $i$-th document using $K_i$ and store $\operatorname{Enc}_K(K_i)$ "next to the document" ie so that you can find this ciphertext when you know which document to access.

The per-user registration goes like this:

• Encrypt $K$ under a user-specific public key. This is what happens upon registration. This public key may be stored symmetrically encrypted on the server using the user's password.

Revokation then works like this:

• Upon revokation pick a new $K'$. Re-encrypt all $K_i$ with that $K'$ and encrypt the new $K'$ under the public keys of all the users and replace the old encryptions of $K$.

Accessing a document then goes like this:

1. The user retrieves their private-public keypair.
2. The user requests their encrypted copy of $K$ and decrypts it.
3. The user requests a document with its encrypted per-document key, decrypts this key and decrypts the document.

Because this question will probably come up:

Why not use the global key to encrypt all the documents directly?

The idea is to a) limit the amount of ciphertext available under a single key and b) that if some user has access, they learn $K$, and so you would have to actually re-encrypt all the documents after their access gets revoked in case an admin leaks the ciphertext blobs. If you also update the per-document key on each document update any user will only be able to decrypt documents they have already seen this way.

Answer 2

Proxy re-encryption (PRE) works well for this situation - each document is encrypted with a random symmetric key, and that key is encrypted using PRE to a group's public key. The system admins can compute a re-encryption key from the group to each of the users' public keys. Revocation is as simple as deleting the re-encryption key. This avoids the necessity of re-encrypting all the documents if access is revoked for a user.

A paper about using PRE for situations like this is available here, and it references some of the seminal papers introducing PRE. (A paper that describes this in detail is available here (this directs through my company's website to the ACM digital library - sorry for the extra hop, but it avoids the need to have ACM Digital Library access to get the paper). The 2006 paper "Improved Proxy Re-encryption Schemes with Applications to Secure Distributed Storage" by G. Ateniese, K. Fu, M. Green, and S. Hohenberger is an important one that is often cited.

Supporting search is trickier in this situation though. You could maintain the search index in the client - when it adds a new document, it would need to extract the keywords, retrieve the encrypted index, add the new pointers, and encrypt it again.