Search Over Encrypted Data

Question

I'm doing a research about how to search over encrypted data as the title said. And, I saw cryptDB used a cryptographic scheme from Song et.al's article Practical Techniques for Searches on Encrypted Data to search for words on encrypted data. But why they don't use DET encryption for each word and to search for a word just encrypt a word and compare it?

Answer 1

If you encrypt the words with the ECB mode then it will reveal information which we call frequency attack. The attacker can see which words are repeating among the rows and try to extract information especially if the attackers have some knowledge of the data contained in the database.

We can see this in a small SEARCH column if encrypted with ECB mode;

| ID  |...| SEARCH                                         |
| x01 |...| 0xF41, 0x650, 0x086, 0x331 ....                |
| x02 |...| 0xF41, 0x165, 0x086, 0x63f, 0x754 ....         |
| x03 |...| 0x650, 0x331, 0x1E6, 0x12f, 0x004 ....         |

As you can see, if you use the ECB mode directly, you can extract information from the SEARCH rows. Using ECB column in CryptDB is your choice. If you think that the data is vulnerable to attack, don't use the ECB mode.

Instead of using ECB, they choose to Song's work and modified as;

They split the words with standard delimiters, removed the repetitions, randomly permuted the repeated words, padded each word into the same size then encrypted.

They claim that their SEARCH nearly as secure as their RND mode, CBC mode with randomized IV for each encryption. They also claim that DBMS server cannot distinguish whether a word repeats in multiple rows and it only leaks the number of distinct words by comparing the size of RND column and SEARCH column.

It is not clear from their article that how this effect the performance. Actually, it is clear that the encryptions with different keys for each row are not performed on the Database. The whole burden of the system is based on the Proxy-Server, and the overhead to the proxy server is not measured for the article.

Answer 2

The big problem with a plain deterministic encryption and search method, is that it makes the scheme very fragile against dictionary attacks and brute force attacks. It allows an adversary to efficiently perform statistical attacks against the dataset, in order to gain information and this is not something desirable when dealing with encrypted data. Fundamentally, the ideas behind Song's scheme are relying on deterministic encryption and deterministic pseudo-random streams, but they did improve on top of the "simplest" way to do it, in order to try and avoid a couple problems.

The goal behind Song's scheme is to achieve better security than the simple method, this is notably why they rely on the notion of "probabilistic searches": when searching for a given word, the scheme returns all the positions where this word occurs in the plaintext, as well as possibly some other wrong positions.

You are correct saying that when looking into search over encrypted data, deterministic encryption schemes are one of the simplest way to get a solution, but they are lacking in several aspects:

Firstly, your encrypted dataset and search keywords will leak information to the server. Since you are using a deterministic encryption scheme, when looking up a given keyword, notice that the same keyword will always encrypt to the same ciphertext.

Most notably, this means that the server can check and sees how many occurrences of a given ciphertext appear in the dataset, and it also leaks the corresponding encrypted documents contain a keyword in common. This makes deterministic schemes prone to frequency analysis. Notice that Song's scheme is not really addressing this problem, although they do propose a workaround in section 5.2.

The next problem is that since it uses deterministic encryptions, the server will always know when a client is searching multiple time the same thing. Notice that this problem is not addressed by Song's scheme.

Now, a third problem that can also occur is that the deterministic encryption scheme could be a public-key scheme. Which means that all the encryptions are done using the client's public key. Since it is public, the server can easily pull of a dictionary attack on the encrypted dataset by creating itself a list of encrypted keywords and comparing them to the ones found in the encrypted dataset, or in the search queries. As soon as it finds a match, it has found the cleartext equivalent...

Finally, if you are interested by a "simpler, deterministic method" than Song's scheme, you can read the following by Bellare et al regarding deterministic, searchable encryption: https://eprint.iacr.org/2006/186.pdf

In the end, Song's scheme really is based on deterministic encryption, and does just improve the state of the art w.r.t it.