[Tryk]

When comparing two ciphertexts A,B a FHE sorting function will output a sorted pair of two new ciphertexts:

E.g. FHE_SORT(A,B) -> (X,Y)

where Dec(X)<Dec(Y)

But without decoding, there's no way of knowing whether X (or Y) comes from A or B.

Source: II. D of https://eprint.iacr.org/2015/995.pdf

[dcow]

It’s not that simple. The client has to send the server the comparison function.

To do anything practical the server usually needs to provide the client with gigabytes of per-client-key encrypted seed data.