[littlecranky67]

I get how that works for arithmetic operations - what about stuff like sorting, finding an element in a set etc? This would require knowledge of the cleartext data, wouldn't it?

[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

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

[gadders]

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

[j2kun]

Comparisons can be implemented by approximating a < b with

    0.5 * (sign(a - b) + 1)

And the sign function can be approximated by a polynomial that uses only additions and multiplications and products with constants.

Other FHE schemes have support for small-bitwidth lookup tables that makes supporting comparison more direct.