18 ms·
A very basic way of how it works: encryption is basically just a function e(m, k)=c. “m” is your plaintext and “c” is the encrypted data. We call it an encrypti
by dachrillz 1y ago
A very basic way of how it works: encryption is basically just a function e(m, k)=c. “m” is your plaintext and “c” is the encrypted data. We call it an encryption function if the output looks random to anyone that does not have the key
If we could find some kind of function “e” that preserves the underlying structure even when the data is encrypted you have the outline of a homomorphic system. E.g. if the following happens:
e(2,k)*e(m,k) = e(2m,k)
Here we multiplied our message with 2 even in its encrypted form. The important thing is that every computation must produce something that looks random, but once decrypted it should have preserved the actual computation that happened.
It’s been a while since I did crypto, so google might be your friend here; but there are situations when e.g RSA preserves multiplication, making it partially homomorphic.
- littlecranky67 1y agoI 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 1y agoYou 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]
- j2kun 1y agoComparisons 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.
- xhrpost 1y agoThis made me wonder if there is such a thing as homomorphic compression. A cursory search says yes but seems like limited information.
- Tryk 1y agoWhat do you mean by homomorphic compression? Given that the operations you can execute on the ciphertext are Turing complete (it suffices to show that we can do addition and multiplication) then it follows that any conceivable computation can be performed on the ciphertext.
- xhrpost 1y agoOh this is outside the context of encryption. My curiosity was, is there such a compression function that permits operations on the compressed data without first decompressing it?
- dachrillz 1y agoOne that is kind of in this spirit is that you can describe sparse matrices by omitting all the zeros and only describe the indices that have data. In this compression you can still perform normal matrix operations without having to unpack them into the “normal form”. Now this is neither encryption nor a particularly interesting compression, but it does prove that it is possible in principle ;p
- JohnFen 1y ago> If we could find some kind of function “e” that preserves the underlying structure even when the data is encrypted But isn't such a function a weakened form of encryption? Properly encrypted data should be indistinguishable from noise. "Preserving underlying structure" seems to me to be in opposition to the goal of encryption.
- paulrudy 1y agoThank you, this really clarified things for me!