Frequency Attacks on Encrypted Database

Question

I'm trying to build an encrypted database where we can't trust on the database manager. And since encrypt data in a deterministic way is bad, attackers can recover information doing frequency attacks, I had the following idea:

|Names         |bucket|
|0xF32(Michael)|2     |
|0x321(Simon)  |1     |
|0xG3F(Simon)  |1     |
|0xT2A(Ana)    |1     |

As u can see Names is encrypted in a random way, and the bucket is calculated with some function where f(Simon) = 1; And now if a client wanna get all Simons in the database he will execute f(Simon) =1 and query the database where the bucket value = 1. In this way, database will give to client Simon and Ana's value. And the client will discard Ana. In this way, database will not know what values correspond to Simon.

My main problem is a way to get a function where it gives me collisions but not a lot.

Answer 1

The problem

Frequency attack is a big problem for databases. For example, these two 1 2 articles represent the attack in CryptDB. This can have serious results, especially if you consider that the encryption is enough. You can find more about frequency attack if you search. There is no clean solution if you have to query over the encrypted data and if you don't know about the distribution of the columns.

The pioneer work

Hacıgumüş et. al was a pioneer in this subject; Executing SQL over Encrypted Data in the Database-Service-Provider Model. Their work used partitioning of the data into buckets. The first column etuple contains the encryption of the columns in concatenate form and the columns are bucketed. You query over the bucket columns and decrypt the etuple on the returned query result. On section 2.1 you can find partition example functions.

Using hash

Using a trimmed hash function at first may seem like a solution but not necessary. We are not under control of the output of the hash functions. The two most frequent data in a column may have the same trimmed hash result. Therefore one needs to check the buckets.

Another not enough solution

There was an article about, that I couldn't find it¹, was proposing dividing the data into equal size buckets. This works requires preknowledge of the frequency.

The technique was in the simple term normalizing the data into buckets that is differs from your solution. For example; assume that we have 5 different data in a column with the following name and amounts; $\{(a,5),(b,10),(c,20),(d,40),(e,25)\}$ then they proposed to partition into buckets that can contain at most 10 elements;

$$\{(a,5,10), (b,10,10),(c_1,10,10),(c_2,10,10), (d_1,10,10),(d_2,10,10),(d_3,10,10),(d_4,10,10), (e_1,10,10),(e_2,10,10),(e_3,5,10) \}$$ where the sub indexes are different encryption of same value, that can be satisfied by a fixed IV for CBC mode per bucket.

For the query, you have to store the bucket information in your appliaction server. Wait; if attackers see the row count of returned result from the DB, they can identify some buckets. For example, if you query $a$ they can know that it is either $a$ and $b$.

---

Note 1: If you are not carefully bucketing, the row count will have a similar result for bucketing. For this one may assume that the attacker has limited time on the attack and can say only a few queries may be leaked. This totally depends on your risk analyzes.

Note 2: if the frequency of the data changes over time, you may need to re-bucketing

---

¹ I'll link if I can find someday.