4 ms·

> FHE enables computation on encrypted data This is fascinating. Could someone ELI5 how computation can work using encrypted data? And does "computation" appl

> FHE enables computation on encrypted data This is fascinating. Could someone ELI5 how computation can work using encrypted data? And does "computation" apply to ordinary internet transactions like when using a REST API, for example?

pluto_modadic 1y ago
a simple example of partial homomorphic encryption (not full), would be if a system supports addition or multiplication. You know the public key, and the modulus, so you can respect the "wrap around" value, and do multiplication on an encrypted number. other ones I imagine behave kinda like translating, stretching, or skewing a polynomial or a donut/torus, such that the point/intercepts are still solveable, still unknown to an observer, and actually represent the correct mathematical value of the operation. just means you treat the []byte value with special rules
- paulrudy 1y ago
  Thank you. So based on your examples it sounds like the "computation" term is quite literal. How would this apply at larger levels of complexity like interacting anonymously with a database or something like that?
  - strangecasts 1y ago
    There are FHE schemes which effectively allow putting together arbitrary logical circuits, so you can make larger algorithms FHE by turning them into FHE circuits -- Jeremy Kun's 2024 overview [1] has a good summary [1] https://www.jeremykun.com/2024/05/04/fhe-overview/ https://www.jeremykun.com/2024/05/04/fhe-overview/ - discussed previously: https://news.ycombinator.com/item?id=40262626 https://news.ycombinator.com/item?id=40262626
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 ago
  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 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 ago
      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 1y ago
        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 https://eprint.iacr.org/2021/551.pdf
      - gadders 1y ago
        Honestly it breaks my brain as well. I just have to take it on trust that it apparently works.
      - Tryk 1y ago
        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 https://eprint.iacr.org/2015/995.pdf

pluto_modadic 1y ago

a simple example of partial homomorphic encryption (not full), would be if a system supports addition or multiplication. You know the public key, and the modulus, so you can respect the "wrap around" value, and do multiplication on an encrypted number. other ones I imagine behave kinda like translating, stretching, or skewing a polynomial or a donut/torus, such that the point/intercepts are still solveable, still unknown to an observer, and actually represent the correct mathematical value of the operation. just means you treat the []byte value with special rules

paulrudy 1y ago
Thank you. So based on your examples it sounds like the "computation" term is quite literal. How would this apply at larger levels of complexity like interacting anonymously with a database or something like that?
- strangecasts 1y ago
  There are FHE schemes which effectively allow putting together arbitrary logical circuits, so you can make larger algorithms FHE by turning them into FHE circuits -- Jeremy Kun's 2024 overview [1] has a good summary [1] https://www.jeremykun.com/2024/05/04/fhe-overview/ https://www.jeremykun.com/2024/05/04/fhe-overview/ - discussed previously: https://news.ycombinator.com/item?id=40262626 https://news.ycombinator.com/item?id=40262626

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 ago
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 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 ago
    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 1y ago
      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 https://eprint.iacr.org/2021/551.pdf
    - gadders 1y ago
      Honestly it breaks my brain as well. I just have to take it on trust that it apparently works.
    - Tryk 1y ago
      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 https://eprint.iacr.org/2015/995.pdf