Thanks for posting, very interesting project!

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.