Suppose I am storing a number of encrypted documents in a database. I would like to make it possible to identify the subset of documents whose contents match user-specified search terms without a) maintaining a plaintext index or b) decrypting documents on the fly. Is there any way to accomplish this securely?

By the same token, I'm wondering if a collection of encrypted documents can be sorted according to an encrypted attribute (e.g., document title) without first decrypting all attribute values.


Yes. If you encrypt the documents with this purpose in mind (you have to use a special kind of encryption algorithm), then yes, it is possible to do this, for certain kinds of search queries.

There is a rich research literature on this topic. The buzzword is "search on encrypted data". I'll point you to a few sample papers in this space. Do a literature search, and you should be able to find many more for yourself.

The best scheme for your situation will depend upon your application requirements. If you have a read-mostly database (updates are rarer than searches), then I would suggest a scheme based upon encrypted indexes. If you need to make modifications frequently, or if searching is relatively rare, the other schemes might be preferable.

  • $\begingroup$ I'll put this in a comment because it's not directly related: 'Structured Encryption and Controlled Disclosure' Chase and Kamara 2011 $\endgroup$
    – pg1989
    Aug 21 '13 at 18:54

Well, if you have documents encrypted with SHA512 or MD5 or any one-way crypto, the only possibility you have is to encrypt search terms with the same crypto and make the query to the DB.

  • $\begingroup$ You'll have to add more detail here. Simply doing this does not work because of the all-or-nothing property, H("keyword") is designed to be independent of H(document containing "keyword"). You need a more elaborate scheme for this to work. $\endgroup$
    – Thomas
    Aug 4 '12 at 2:18
  • $\begingroup$ You're right. I forgot that. Sorry. $\endgroup$ Aug 4 '12 at 2:27
  • 3
    $\begingroup$ SHA512 and MD5 are not encryption. They are hashes. $\endgroup$
    – D.W.
    Aug 4 '12 at 21:48
  • $\begingroup$ Yes, just yesterday I read that in a blog about IT security. $\endgroup$ Aug 23 '12 at 20:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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