How to do statistical analysis on encrypted / anonimized data

Question

Let's imagine Alice wants to send Bob a table with 2 columns:

+----------+-----+
| location | age |
+==========+=====+
| ny       | 22  |
+----------+-----+
| london   | 23  |
+----------+-----+
| ny       | 18  |
+----------+-----+
| paris    | 25  |
+----------+-----+
| madrid   | 28  |
+----------+-----+
| london   | 35  |
+----------+-----+

Bob will receive this data and perform some stats over it. The result will be send back to Alice:

+----------+-------------+
| location | average age |
+==========+=============+
| ny       | 20          |
+----------+-------------+
| london   | 29          |
+----------+-------------+
| paris    | 25          |
+----------+-------------+
| madrid   | 28          |
+----------+-------------+

However, Alice doesn't want Bob to know the "location" of the individuals (it is irrelevant to perform the average function).

Instead Alice wants to send the first column converted to an "hash" (in terms of keeping coherence between equal values; and the output string has the same length independently of the input string) BUT she should be able to "unhash" the receiving Bob's table (without storing any dictionary that translates the "hashes" into the original strings).

Alice sends:

+----------------------------------+-----+
| location                         | age |
+==================================+=====+
| 531beb50ffb32d08756e6462c037c8e1 | 22  |
+----------------------------------+-----+
| bc180dbc583491c00f8a1cd134f7517b | 23  |
+----------------------------------+-----+
| 531beb50ffb32d08756e6462c037c8e1 | 18  |
+----------------------------------+-----+
| ccbee73cd81c7f42405e1920409247ec | 25  |
+----------------------------------+-----+
| ed2539fe892d2c52c42a440354e8e3d5 | 28  |
+----------------------------------+-----+
| bc180dbc583491c00f8a1cd134f7517b | 35  |
+----------------------------------+-----+

and receives:

+----------------------------------+-------------+
| location                         | average age |
+==================================+=============+
| 531beb50ffb32d08756e6462c037c8e1 | 22          |
+----------------------------------+-------------+
| bc180dbc583491c00f8a1cd134f7517b | 29          |
+----------------------------------+-------------+
| ccbee73cd81c7f42405e1920409247ec | 25          |
+----------------------------------+-------------+
| ed2539fe892d2c52c42a440354e8e3d5 | 28          |
+----------------------------------+-------------+

1st approach:

Alice should send a key (in the message heading) to Bob.

Bob, together with his response, will send the same key back (again, in the response heading) to Alice.

[alternative method is proposed after]

---

This key is valid just for that request and gives Alice a way to decrypt the "hashes" back to the original values:

+----------+-------------+
| location | average age |
+==========+=============+
| ny       | 20          |
+----------+-------------+
| london   | 29          |
+----------+-------------+
| paris    | 25          |
+----------+-------------+
| madrid   | 28          |
+----------+-------------+

2nd approach:

The envelope of this message is also encrypted asymmetrically and it should be alright to use traditional client identification (such as client key exchange message in elliptic curves) together with session key, as the final key that generates the symmetric transformation (avoiding sending another key on the heading as proposed before).

---

In conclusion,

• Equal origin strings should be converted into equal ciphertext strings (for each session)
• Different sessions should produce different ciphertexts for the same string
• Alice should be able to decrypt the ciphertext string into the original one, without storing a dictionary (unlike what happens when using unidirectional hashes)
• The decrypt key should preferably reuse the generated keys that protect the communication envelope, to avoid redundancies or unnecessary information
• Bob should never be able (well, should be very difficult) to reverse engineering the encryption data of a transaction or by collecting multiple transaction's messages (although he could know the mutable part of the key)
• The transformation string should always have the same length (so Bob couldn't identify "ny" because its short length)

Any ideas?

Answer 1

This type of problem is known as anonymizing data, and it has fairly standard solutions.

The obvious way is to use a Format Preserving Encryption method; that is a secret key method that has a fairly arbitrary domain. Because Alice is the only one who needs to be able to encrypt and decrypt, she can generate the key locally, and never distribute it.

If we assume that the longest city name you'll want to handle has 32 characters, then you'll have the FPE encryption domain be 32 characters, each of which is either a lower case letter, an upper case letter, or a space (do you have any cities with characters outside this range? If so, you'd throw those in as well).

Alice would pick a random key (and yes, this is a key in the cryptographical sense, not the database sense you used the term). Then, to encrypt, she'd take the city name, pad it out with spaces so that it'll the full 32 characters long, and then pass it to the encryptor; that'd return a random-looking string that's 32 characters long. Decryption is similar; you'd pass in the ciphertext and the cryptographical key to the decryption algorithm, which would return a 32 character string (which you'd trim off the trailing spaces to restore the original name).

Equal origin strings should be converted into equal ciphertext strings (for each session)

Yes, given the same string and key (and tweak, see next answer), FPE always returns the same ciphertext

Different sessions should produce different ciphertexts for the same string

There are two ways to handle this:

• FPE algorithms provide a tweak to handle exactly this case; you can make the session id the tweak (which you'd hand to the encryption and decryption functions)

• Alternatively, just generate a fresh random key for each session

Alice should be able to decrypt the ciphertext string into the original one, without storing a dictionary (unlike what happens when using unidirectional hashes)

Yes, decryption is easy (as long as you have the key)

The decrypt key should preferably reuse the generated keys that protect the communication envelope, to avoid redundancies or unnecessary information

Yes, FPE uses the same keys to encrypt and decrypt

Bob should never be able (well, should be very difficult) to reverse engineering the encryption data of a transaction or by collecting multiple transaction's messages (although he could know the mutable part of the key)

Yes, there are believed-secure FPE algorithms

The transformation string should always have the same length (so Bob couldn't identify "ny" because its short length)

That's why we space-pad out the string to 32 characters.