I implemented something similar at the company I work with:
1. All private data is encrypted/decrypted client side using envelope encryption: a random AES key is generated to encrypt the data, and then we use KMS (which are basically the same services in both AWS and GCP) to encrypt the AES key with a public key. Thus, storing data requires no KMS API call to encrypt data, but decryption does. But we basically have per-user AES keys, and since our data access patterns are largely per-user it means we can cache the decrypted key.
2. We use blind indexes for lookups.
3. We then hit the issue of needing to order on encrypted data, and we used one of the order-respecting encryption algos but your explanation was super helpful to me! I'll definitely look more into the Lewi-Yu scheme.
All in all a very cool project I look forward to digging in more. I haven't looked yet at how you store/retrieve the encryption keys but integration with a service like KMS would be great. For us it is ideal because all calls to KMS are auditable so we can audit exactly when data was decrypted.
The only problem with KMS in this model is that to get that auditability you need a data key per value/record. That means every decryption requires a request to KMS as it does not (and likely won't ever) support batched requests. We tried this for ages and the performance was terrible. < 100ms queries blew out to over 3 or 4 seconds.
Only if you need the auditability at that granular a level.
For us, each user has (for the most part) their own data key, and most of the time a user is accessing their own data. So we can decrypt the key once and then cache it for the rest of the user's session. This tells us "the user accessed their private data", so we don't get the per value auditability, but for us that was sufficient. If you want, you could even have different data keys based on sensitivity, e.g. a user's name, phone, address is encrypted with one data key but their SSN or credit info is encrypted with another.
That's true except that if that session key is lost or exfiltrated, the scope of the breach is everything that key was used to encrypt (all of the user's data in your example).
The other consideration is how to safely cache the data key? What if the cache is popped?
I implemented something similar at the company I work with:
1. All private data is encrypted/decrypted client side using envelope encryption: a random AES key is generated to encrypt the data, and then we use KMS (which are basically the same services in both AWS and GCP) to encrypt the AES key with a public key. Thus, storing data requires no KMS API call to encrypt data, but decryption does. But we basically have per-user AES keys, and since our data access patterns are largely per-user it means we can cache the decrypted key.
2. We use blind indexes for lookups.
3. We then hit the issue of needing to order on encrypted data, and we used one of the order-respecting encryption algos but your explanation was super helpful to me! I'll definitely look more into the Lewi-Yu scheme.
All in all a very cool project I look forward to digging in more. I haven't looked yet at how you store/retrieve the encryption keys but integration with a service like KMS would be great. For us it is ideal because all calls to KMS are auditable so we can audit exactly when data was decrypted.