4 ms·
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 c
by barisozmen 1y ago
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 1y agoWhile 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 1y agoYou 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 https://eprint.iacr.org/2021/551.pdf
- gadders 1y agoHonestly it breaks my brain as well. I just have to take it on trust that it apparently works.
- Tryk 1y agoWhen 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 https://eprint.iacr.org/2015/995.pdf
- dcow 1y agoIt’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.
- deleted 1y ago[deleted]