[barisozmen]

You can reduce anything happening on the computer to arithmetic operations. If you can do additions and multiplications, then it's turing complete. All others can be constructed from them.

[littlecranky67]

While correct, that doesn't answer the question at all, though. If I have my address book submited into an FHE system and want to sort by name - how do you do that if the FHE system does not have access to cleartext names?

[barisozmen]

You can do that by encrypting the names. You send encrypted names to the FHE-server, and then the server does necessary sorting computations on it.

The point of FHE is it can operate on gibberish-looking ciphertext, and when this ciphertext decrypted afterwards, the result is correct.

Indeed, there are those working on faster FHE sorting: https://eprint.iacr.org/2021/551.pdf

[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

[gadders]

Honestly it breaks my brain as well. I just have to take it on trust that it apparently works.