2 ms·

Here's what I don't understand about homomorphic encryption and so struggle to trust in the very concept. If you can process encrypted data and get useful resul

Here's what I don't understand about homomorphic encryption and so struggle to trust in the very concept. If you can process encrypted data and get useful results, then a major part of the purpose of encryption is defeated, right? How am I wrong?

ramchip 1y ago
The result is encrypted. It's useful to the key holder, not to the party doing the computation.
- JohnFen 1y ago
  Yes, I understand that part. The part I struggle with is how the very fact that a party without the key can do the computation on it is not an indication that the encryption is leaking information. If the encryption were airtight, then such computation shouldn't be possible. Given that cryptography experts seem to be asserting otherwise, I assume that there's something important that I'm not understanding here.
  - prophesi 1y ago
    The tl;dr is that breaking FHE would mean solving lattice problems that have been studied for decades to be nontrivial to break[0]. [0] https://arxiv.org/abs/2208.08125 https://arxiv.org/abs/2208.08125
    - JohnFen 1y ago
      I'm not talking about the possibility of breaking FHE, though. What I don't understand is this: if I get encrypted data from someone and, without breaking that encryption, I can perform computations on it that yield a sensible result (even if the result is also encrypted with a key I don't have), then how does that not mean the encryption has been weakened? If the encryption were strong, that should not be possible. Actually breaking the encryption is a different thing, and I wasn't questioning that.
      - prophesi 1y ago
        The operations used to perform these computations are utilizing algorithms backed by lattice-problems that are NP-hard to break. edit: The only leaking information in this case are what operations you'd like to perform on the encrypted data. e.g., you now know that you've incremented the password by x amount, but you don't know what the plaintext was before, the plaintext after, _or_ infer what the value is by knowing you've modified the encrypted data by x amount. edit2: Now I think I understand the question. The encryption is technically weakened because you can know what operations are made on the underlying data. Though it's still an advancing field, and there are promising developments with what's called circuit privacy[0] to prevent the server knowing the operations made as well. [0] https://eprint.iacr.org/2022/1459 https://eprint.iacr.org/2022/1459
      - j2kun 1y ago
        Your assumption that operations leak info is just not correct. RSA has homomorphic properties (you can multiply two RSA ciphertexts and get the encrypted product of the plaintext), just not enough to enable general purpose computation.
        JohnFen 1y ago
        > Your assumption that operations leak info is just not correct. My assumption is that you're right, that my assumption is incorrect. What I'm trying to do is understand why it's incorrect. It's not just about operations leaking info, though, it's also an issue that, intuitively, leaving enough underlying structure in the encrypted form of the data to allow for this implies that the encrypted form is weaker. I'm also trying to understand how that intuition is wrong. Edit: OK, The jeremykun link this comment provided gave me a little more clarity: https://news.ycombinator.com/item?id=44602472 https://news.ycombinator.com/item?id=44602472 I still don't adequately understand, but it does give me a little bit of a handle my brain can grab onto. As I understand it right now, HME is a weaker form of encryption, but perhaps still strong enough to be a worthwhile tradeoff for the use cases being discussed.
        j2kun 1y ago

ramchip 1y ago

The result is encrypted. It's useful to the key holder, not to the party doing the computation.

JohnFen 1y ago
Yes, I understand that part. The part I struggle with is how the very fact that a party without the key can do the computation on it is not an indication that the encryption is leaking information. If the encryption were airtight, then such computation shouldn't be possible. Given that cryptography experts seem to be asserting otherwise, I assume that there's something important that I'm not understanding here.
- prophesi 1y ago
  The tl;dr is that breaking FHE would mean solving lattice problems that have been studied for decades to be nontrivial to break[0]. [0] https://arxiv.org/abs/2208.08125 https://arxiv.org/abs/2208.08125
  - JohnFen 1y ago
    I'm not talking about the possibility of breaking FHE, though. What I don't understand is this: if I get encrypted data from someone and, without breaking that encryption, I can perform computations on it that yield a sensible result (even if the result is also encrypted with a key I don't have), then how does that not mean the encryption has been weakened? If the encryption were strong, that should not be possible. Actually breaking the encryption is a different thing, and I wasn't questioning that.
    - prophesi 1y ago
      The operations used to perform these computations are utilizing algorithms backed by lattice-problems that are NP-hard to break. edit: The only leaking information in this case are what operations you'd like to perform on the encrypted data. e.g., you now know that you've incremented the password by x amount, but you don't know what the plaintext was before, the plaintext after, _or_ infer what the value is by knowing you've modified the encrypted data by x amount. edit2: Now I think I understand the question. The encryption is technically weakened because you can know what operations are made on the underlying data. Though it's still an advancing field, and there are promising developments with what's called circuit privacy[0] to prevent the server knowing the operations made as well. [0] https://eprint.iacr.org/2022/1459 https://eprint.iacr.org/2022/1459
    - j2kun 1y ago
      Your assumption that operations leak info is just not correct. RSA has homomorphic properties (you can multiply two RSA ciphertexts and get the encrypted product of the plaintext), just not enough to enable general purpose computation.
      - JohnFen 1y ago
        > Your assumption that operations leak info is just not correct. My assumption is that you're right, that my assumption is incorrect. What I'm trying to do is understand why it's incorrect. It's not just about operations leaking info, though, it's also an issue that, intuitively, leaving enough underlying structure in the encrypted form of the data to allow for this implies that the encrypted form is weaker. I'm also trying to understand how that intuition is wrong. Edit: OK, The jeremykun link this comment provided gave me a little more clarity: https://news.ycombinator.com/item?id=44602472 https://news.ycombinator.com/item?id=44602472 I still don't adequately understand, but it does give me a little bit of a handle my brain can grab onto. As I understand it right now, HME is a weaker form of encryption, but perhaps still strong enough to be a worthwhile tradeoff for the use cases being discussed.
        j2kun 1y ago