You all might be aware of this, so please excuse the redundant information:
CryptDB http://css.csail.mit.edu/cryptdb/ CryptDB is a system that provides practical and provable confidentiality in the face of these attacks for applications backed by SQL databases. It works by executing SQL queries over encrypted data using a collection of efficient SQL-aware encryption schemes. CryptDB can also chain encryption keys to user passwords, so that a data item can be decrypted only by using the password of one of the users with access to that data. As a result, a database administrator never gets access to decrypted data, and even if all servers are compromised, an adversary cannot decrypt the data of any user who is not logged in CryptDB is MySQL based system, but I think that some of its mechanisms could be relevant for key-value stores. (In my work/research, I was looking for HIPAA compliant data store) Regards, Edmon
