[JohnFen]

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.

[InfoSecErik]

I think the disconnect is that you assume that being able to do useful computation on some data implies that it must be possible to derive some insight into what the data is (side-channels or the like).

It's a fair assumption to start with. But the folks building FHE basically claim "nuh-uh", and I haven't seen anything to indicate they're wrong. Maybe some new Math grad will sort it out.

[j2kun]

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]

> 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

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.

[plopilop]

> 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.

Exactly. Homomorphism was first seen as a weakness in encryption, since it implies malleability. For instance, in the one-time pad encryption where you XOR your message with the secret key, flipping a bit in the ciphertext will result in same bit being flipped in the decryption. The attacker does not know what the end result is, but knows that the bit has been flipped, hence OTP encryption is malleable. This is enough for some attacks. With FHE encryption you have a bit of the same, from Enc(a) and Enc(b) it is easy to create Enc(a+b), hence is malleable too.

Cryptography uses several security levels. The top one for encryption is NM-CCA2 (non-malleability under chosen ciphertext attack). For instance, RSA-OAEP is NM-CCA2 secure. Since FHE schemes are malleable, they are not NM-CCA2 secure. However, a slightly lower security notion is IND-CPA (indistinguishability under chosen plaintext attack). FHE schemes are IND-CPA secure. Furthermore, IND-CPA security is shown to be equivalent to semantic security, which means that given a ciphertext the attacker cannot know any bit of information about the underlying cleartext.

Hence, FHE schemes guarantee that for all the ciphertexts they receive, the attacker cannot know anything about the underlying cleartexts. You can run a ton of operations on the ciphertexts, let's say run a homomorphic LLM, the attacker will still have no idea about what the final output is. Hence, in the model where you consider that the attacker has full control over the LLM, will behave honestly but will try to learn your secrets, you are fine. However, in the model where an attacker runs a MITM and just wants to disrupt the numbers you get back from the LLM, then you are not fine, since this encryption is malleable (in theory we could add some verifiable execution proofs but that is another topic).

As you say, everything is a tradeoff.

[j2kun]

All modern cryptography is based on problems with some mathematical structure. With enough structure it's true, it does weaken security, and many cryptosystems are broken by exploiting the underlying structure. So I suppose the only solid answer here is that attacks haven't been discovered yet despite many smart people trying.

[JohnFen]

Heh, I didn't realize that you were the Jeremy Kun that wrote the piece that gave me a bit of enlightenment (that I mentioned in the edit to my comment above). Thank you for writing that. It was helpful.

[prophesi]

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