As for now, we only need equality operator, so we use deterministic encryption for deks and handle keks in vaults. Kek rotation is kind of a pain, so we index edeks in order to improve our queries, which basically build dynamic UNION ALL or IN statements.
I’m sure is not the most secure schema in the world, but it makes retrieval fast and most analytics can be worked out with dynamic query building, while making the db a scrambled mess for those with partial access.
It sounds like both of you do something very similar to what we do. Our data keys are themselves encrypted by AWS KMS. The data keys are decrypted and kept in memory on application startup. They are stored encrypted in S3.
It’s kind of like a sparse matrix of encrypted vs. plain data, and works great for our scenario.