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.
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.