Information Security Stack Exchange is a question and answer site for information security professionals. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

I have been reading some very interesting academic papers regarding the ability to search encrypted data without needing to actually decrypt the data. Doesn't this defeat the purpose of encryption in the first place? I can imagine language-specific "brute force" attacks in which I re-assemble the plain text from the encrypted text simply by searching for "interesting" combinations of words.

What is the current practical state of the art in searching encrypted storage and why do we want it? What problem does it actually solve, or are the problems entirely manufactured due to other current environmental conditions (eg. searching sensitive information on the "cloud")?

share|improve this question
2  
Related search: Homomorphic Encryption – LamonteCristo Dec 31 '11 at 19:59
up vote 8 down vote accepted

The "safe" versions of searching in encrypted data assume at least one of the following:

  • the pattern to search for is also encrypted with the same key (or some kind of related key) than the data itself;
  • the search result ("pattern was found there") is encrypted with the same key (or some kind of related key) than the data itself.

With either of these properties, the search engine does not leak information on the data to someone who would not be able to decrypt it in the first place.

The ultimate goal is to be able to offload the grunt work of searching to a big cloud system, while not needing to trust that system. Fully homomorphic encryption is the generic full-blown solution for offloading any kind of work, and the best currently known solutions for that are utterly unreasonable to apply because the overhead is tremendous (it can be implemented, but there is little use in offloading work to a cloud if the result is something slower than a pocket calculator). Encrypted data searching is a specialization: by restricting ourselves to a specific kind of work to offload (i.e. searching), we hope to find algorithms which are sufficiently lightweight to have a practical application.

To my knowledge, the field has not produced anything practical yet (but there is no intrinsic reason why it could not).

share|improve this answer

An important thing to remember about searching encrypted data is who the data owner is. In a number of proposals/papers I've seen, the data is owned by the person doing the searching. They are simply utilizing cloud resources to do the searching. This is not true of all schemes, however. For example, SADS.

Another important point to look at when reading these sorts of papers is if it requires a trusted third party (TTP). A TTP could mitigate many attacks that would be possible otherwise (such as brute-forcing documents as you describe).

For the state of the art, you'll need to be more specific about your requirements (who owns the data, who can search the data, is a TTP okay, etc) as schemes can be quite different based on those requirements. In addition to SADS, I'd recommend looking at CryptDB.

share|improve this answer

You may be interested in looking at encrypted search techniques based on Bloom Filters. In these papers you can find some valuable and practical ideas. They could represent a good and practical approach in quite a few scenarios.

share|improve this answer
    
The link you provided for the Bellovin, Cheswick paper wasn't working for me. I found this alternate link though: academiccommons.columbia.edu/download/fedora_content/download/… Also, the OP linked to Secure Indexes in the original question. – mikeazo Jan 3 '12 at 15:46

Why do we need to search? Take the example of sensitive data, like my health record in Microsoft health volt. When I put that data in the cloud, it is stored in a third party data center, which I can't trust because with root access, a hacker or administrator can access that data. To provide security, we encrypt it.

But encryption takes away all capability to search on data. To overcome this problem there is a new trend in searching on encrypted data.

There are 5 ways to search on encrypted data:

  1. homomorphic encryption
  2. structural encryption
  3. property preserving encryption
  4. functional encryption
  5. orem

Three trends to classify searching on encrypted data:

  1. efficiency
  2. security
  3. query expressiveness

Below link give brief explanation:

neelshah.online or neelshah.xyz

You also read Senny Kamara, a Microsoft researcher.

Or outsourcebit blog for further information.

share|improve this answer
    
Please take more care in writing your posts. Your spelling errors make your posts very difficult to read and they are only caused by carelessness in typing. – schroeder Mar 28 at 14:45
    
This does not really answer the question. You mention some topic names that might answer the question, but you do not actually delve into those topics. Can you expand your answer? – schroeder Mar 28 at 14:46

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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