alt Hacker NewsWhile 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?
Replies
Tryk • last Friday at 11:36 AM
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
➕ show 1 reply
gadders • last Friday at 8:55 AM
Honestly it breaks my brain as well. I just have to take it on trust that it apparently works.
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