Today’s mail servers, file servers and other data storage servers typically must be fully trusted since they have complete access to your data and are supposed not to reveal them without your authorization.

To reduce undesirable security and privacy risks it would be desirable to store your data in encrypted form. This usually implies that some functionalities may have to be sacrificed. Unfortunately searching capabilities are quite often compromised by using encryption.

This is a challenging problem because the storage service does not and should not know the encryption key and, on the other hand, the user cannot afford to download all of the potentially relevant documents and decrypt them before performing a local search. Bandwidth, time and local storage constraints make this option impractical, especially if you want to use a mobile device to run keyword searches over remote encrypted data.

A cryptographic scheme aiming to solve this problem should also guarantee that no loss of data confidentiality occurs. More specifically it should respect the following privacy constraints (adapted from Artzi et al., see below):

• Controlled searching - The server cannot learn anything about the contents of documents, except when the user performs a search.
• Hidden queries - The user can search for a set of documents containing a keyword without revealing the keyword to the server.
• Query isolation - From the query result, the server learns nothing about the plain text other than the set of documents that match the query (and possibly the limited statistical information used to perform ranking).
• Update isolation - The server learns nothing more from updates than it would if there were no additional metadata for the purpose of performing searches.

Here is a short list of references to scientific papers that explain the problem and present various solutions. At Clipperz we are investigating some of them and we plan to add encrypted search capabilities to our password manager and secure storage service.

1. Searchable Symmetric Encryption: Improved Definitions and Efficient Constructions by Reza Curtmola, Juan Garay, Seny Kamara, Rafail Ostrovsky
2. Privacy Preserving Keyword Searches on Remote Encrypted Data by Yan-Cheng Chang, Michael Mitzenmacher
3. Encrypted Keyword Search in a Distributed Storage System by Shay Artzi, Adam Kiezun, Calvin Newport, David Schultz
4. Secure Indexes by Eu-Jin Goh
5. Practical Techniques for Searches on Encrypted Data by Dawn Xiaodong Song, David Wagner, Adrian Perrig