# Sorting over encrypted data with different symmetric keys

I'm working on a security project. I need to perform a sorting on the lists of encrypted integers and strings. The encryption used is symmetric. The clients send the encrypted data in a list to the server (encrypted by different symmetric keys, each key is shared b/w a client and the server). On receiving the list, server may again encrypt it using another key shared between the server (such as authentication server) and the service provider's server. If service provider server wish to sort the encrypted data, then how can it be achieved? It cannot decrypt the original messages encrypted by different users' keys. I found a paper, https://eprint.iacr.org/2014/1017.pdf, however, it performs sort over the data encrypted with same key. But in my project requirements are different where each data element is encrypted by a different key of the client. (each key shared b/w a client and the server).

Any help is appreciated.

• it seems that you need to put a bit of trust to some third party in order the latter to transform ciphertexts coming from different users to ciphers seem to be encrypted by a single user. Look at proxy re-encryption techniques – curious Dec 3 '15 at 19:53
• If the symmetric key is shared between the clients and the server, why does the server not just decrypt and sort using the plaintext values? – mikeazo Dec 3 '15 at 20:32
• @mikeazo service provider server cannot decrypt the original messages. The goal of my work is to perform sort over encrypted data. No decryption is required. – user24094 Dec 3 '15 at 20:52
• But you say "The clients send the encrypted data in a list to the server (encrypted by different symmetric keys, each key is shared b/w a client and the server)." If the key is shared with the server, the server can decrypt the data. So why bother with sort over encrypted data? All it does is add complexity and no security since the server has the key. – mikeazo Dec 3 '15 at 21:03
• I think that you are working in the wrong way. You are working on a security project and so you have some goals. You should state the goals, since currently you are stating a partial solution and asking "how can I now sort when I've done everything in this way?". However, it may be much easier if you encrypt the values differently. Is it absolutely essential to encrypt in this way? – Yehuda Lindell Dec 7 '15 at 16:39

In short: What you ask for is impossible.

You want to sort ciphertexts, which are encrypted with different keys, without being able to decrypt them and not knowing the key(s). Let's assume for a moment that this would be possible.

And then there is an attacker, who just gets a single ciphertext. Now, you have to assume that the encryption scheme is public, and everyone can encrypt anything with any key. And there is a certain message space, e.g. a 256 bit integer.

Now the attacker chooses the integer in the middle, encrypts it under any key. With this value and the challenge ciphertext he uses the sort algorithm. Even if the sorting would be randomized, he still could detect his own input - he chose the key for that ciphertext. And from the sorting he now knows if the plaintext in the ciphertext is lower or higher than his own chosen message. If the ciphertext was lower, he will do the same again, with a value in the middle of the lower interval. Basically, this is just a binary search for the plaintext. Therefore, the encryption scheme is insecure even against a ciphertext-only attack.

• It was really interesting to see the connection that you made to a binary search. – Raja Anbazhagan Jul 8 at 6:23

Without a trusted third party (trusted by both authentication server and the service provider server) which can decrypt/sort/re-encrypt, the ability to do what you want (sorting data over the pseudorandom permutations represented by the encryption functions $E_{k_i}$ where $k_i$ is user $i$'s key) would imply that you were using a very insecure symmetric encryption scheme.

• I'm something looking like homomorphic encryption related sorting. Check the link I mentioned. – user24094 Dec 3 '15 at 22:10
• Not necessarily, you could use some kind of key-homomorphic PRF to do key switching, but it would be pretty inefficient. Orders of magnitude slower than symmetric encryption. – pg1989 Jul 1 '16 at 1:30
• There was an NSDI paper this year that had a cute construction of something like this: usenix.org/system/files/conference/nsdi16/…. – pg1989 Jul 1 '16 at 1:31