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?

  • The long and short of this is going to be that you'll need to look at other document stores that support map-reduce. I imagine you've used Azure Table Storage because you're already in the Azure Cloud and it was easily available, but if you can't set up an external index you're just going to need a vendor that supports searching.
    – Mr Cochese
    Dec 11, 2015 at 15:59
  • @MrCochese I wouldn't throw in the towel just yet... creative solutions to our problems are often not as far out of reach as many of us think. Many algorithms have rather simple implementations that are of minimal consequence but solve problems that at first glance appear rather opaque. Dec 11, 2015 at 17:10
  • This kind of encryption is not generally required to comply with HIPAA/HITECH. Are you requiring it because Azure's Table Storage does not provide sufficient at rest encryption or customer isolation? Does Microsoft cover Azure Table storage in your BAA? I use AWS and have not seen such limitations.
    – joshp
    Dec 12, 2015 at 7:48
  • @joshp - as I understand it, Azure Table Storage provides no at rest encryption.
    – Telastyn
    Dec 12, 2015 at 13:31
  • 2
    @Telastyn Of course, this is opinion. But in that case I would probably really want to switch storage products. Unless you have a really strong reason to stay with it, it just makes a substantial extra hurdle and potential liability. Azure has other storage that does provide at-rest encryption (per their docs), as does AWS. Also if MSFT does not cover Table Storage in your BAA, you might be violating your BAA and creating a huge liability for yourselves and your clients. Can't say without knowing your circumstances.
    – joshp
    Dec 13, 2015 at 0:32

1 Answer 1


You could maintain a separate (or as a part of the NoSQL record) store of hashes of the searchable data. The nature of a hash being non-reversible makes it leak far less information than encrypted strings when you have various amounts of the strings available. Then as queries come in, you just hash the query request information and match on hashes. This makes the data less compromisable than the encryption itself, while maintaining the performance of not having to unencrypt all the data.

For further security, if there's any discriminator (like owning organization) you can use for the people executing the query that scopes to the records they're querying on - you could use that as a salt. This would only work if there's a complete match on scoping though: A set of records is only viewable by group A, and group A can only view that set of records; then you can salt the hashes for that group separate from the salt used for group B etc.

Also, if you have a discriminator as above, you can decrypt into memory or do other things that may be costly - on only that particular groups data. Reducing the data scope on each operation like that can allow you to do far more costly things to get your query matches.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.