I am working with a system that is using NoSQL (Azure Table Storage) primarily to house its data. Unfortunately, the work also involves billing and medical records - meaning the data itself will need to be protected. That's fine, we can provide user access to the system, and encrypt that data over the wire and at rest in the NoSQL.
The problem comes because we want that data to also be searchable. Unecrypted, that's not a problem so much - we make the searchable fields row keys and can do range queries. Encrypted, that won't work. Worse it seems as though any sort of trie or similar structure would need to be stored unencrypted, defeating the purpose. Storing partial strings encrypted would make it easy to break the encryption since we would be leaking information about the cleartext.
So far, the only semi-viable solutions I've run across are 1) stop using NoSQL or 2) read the entire set into memory and do the search there.
Neither are particularly thrilling. Is there any other good approach for this confluence of requirements?