4 ms·

Proper encryption means the ciphertext is indistinguishable from noise. So...in order to be able to process on it, you have to make it not indistinguishable fro

by filup 2mo ago

Proper encryption means the ciphertext is indistinguishable from noise. So...in order to be able to process on it, you have to make it not indistinguishable from noise. So I take offense to the term FHE. It's a oxymoron. The whole thing immidiatly stands out as a sham to build trust where it's gone.

pluto_modadic 2mo ago
they could have gone with an oblivious transfer approach (where it's working on what looks like multiple problems at once, you don't know which)
drdeca 2mo ago
Eh? With secret sharing one can do computation on a shared secret where it is provable that no individual party can recover any information about the data with their share alone. I don’t see why you conclude that FHE couldn’t be close to as secure as that. (Like, not information theoretically, but with computationally bounded adversaries.)
- filup 2mo ago
  I'm not saying that you can't design a system for secure cloud computing.
  - drdeca 2mo ago
    You said that FHE is an oxymoron, seemingly on the basis that in proper encryption the ciphertext is indistinguishable from noise, and you think this can’t be true of FHE. I am arguing to the contrary. In the secret sharing multi-party computation schemes, the individual shares of the secret are random and have no information about the plaintext. I see no reason that FHE can’t have ciphertexts indistinguishable from noise.
Ar-Curunir 2mo ago
No, that’s not what proper encryption means. Security for encryption means that cipher texts encrypting distinct messages are indistinguishable. This is called IND-CPA, and FHE satisfies this.
- filup 2mo ago
  How can it possibly pass indcpa. If the model can give me any valuable information about the cipher. Apparently the middle man would know precisely what is contained in the payload.
  - drdeca 2mo ago
    Here’s a very simple one-time-pad style construction for homeomorphic (but not fully homeomorphic) encryption. Suppose the plaintext, ciphertext, and key, are each a natural number modulo 5. The key is selected uniformly at random. The ciphertext is obtained by adding the key to the plaintext (and as a result is also uniform random). Then the ciphertext is sent to the server. The server only has the ciphertext, which is uniform random. The server then adds some integer mod 5 to the ciphertext, producing a new ciphertext, and sends it back to the user. The user then subtracts their key from the new ciphertext to obtain the new plaintext, which is their original plaintext plus the number the server added. At no point in this process did the server learn anything about the user’s plaintext. This is clearly secure. It is also useless, because just adding a number isn’t a useful thing for a server to do (they may as well just send the user the number and let them add it themselves), but that’s because it is a toy example. I suppose if mind uploading were possible, then under FHE it would in principle be possible to take the ciphertext and run the computation of “this mind upload of this person reads the data and provides some output”, and then presumably that uploaded person would have the experience of seeing the plaintext? But it wouldn’t be possible to get any information about the plaintext without the key (or enough brute force to find the key, but that’s why we use big enough keys to make this infeasible).
    - filup 2mo ago
      What does that have to do with incpa? I send this server a question encrypted. It stays encrypted yet the server distinguished my ciphertext enough to produce a coherent reply. That means there was enough information in the ciphertext for the server to perform the inference, even if it was obscured to where it looks indistinguishable, it apparently wasn't. This doesn't remove trust from the equation, it puts the trust directly on the algorithm. Probably one no one can explain to me like I'm 5. But because it's encrypted I am no longer breaking the law by processing on protected data. I imagine very large contracts await on the other side. Lots of money to be made.
flambo 2mo ago
This is actually the magic of FHE. The ciphertext is indistinguishable from noise AND can be computed on, it just looks like different noise. If you believe the underlying cryptographic hardness assumption of LWE/RLWE/etc, then yes Google cannot see any of the input or output of the model.
- filup 2mo ago
  If it only appears indistinguishable from noise, but it's actually not, then it's just deception.
  - drdeca 2mo ago
    They didn’t say that it “appears” indistinguishable from noise, but that it is indistinguishable. It seems like you strongly believe otherwise, but I suspect you don’t have a good reason to, and just find it unbelievable. Do you think you can distinguish it from noise, if given an implementation and the information an adversary would have access to? Of course, you not being able to wouldn’t demonstrate that noöne can. But, it seems like if you had a good reason to believe that an adversary can, that would suggest you might have some idea of how they could do so. And, if you do have such an idea, then, if that idea works, it would be important for others to know, and if it doesn’t, it would presumably benefit your understanding to see why it doesn’t.
    - filup 2mo ago
      >They didn’t say that it “appears” indistinguishable from noise, but that it is indistinguishable. That's the oxymoron. If it was indistinguishable nothing could be gained. It's not about me being able to distinguish it. It's the model provider saying they cant, when they can.
Veserv 2mo ago
You are objectively wrong. The math is straightforward to show that you can operate on a ciphertext securely in some cryptosystems. Consider two integers M1 and M2. Consider RSA with private key (E), public key (D), and public modulus (N). Encrypt(M, E, N) = mod(pow(M, E), N). Decrypt(C, D, N) = mod(pow(C, D), N). mod(Encrypt(M1, E, N) * Encrypt(M2, E, N), N) = mod(Encrypt(M1 * M2, E, N), N). So, for all RSA encryption, multiplying the ciphertexts results in a ciphertext that is the multiple of the plaintexts. However, unless you can break RSA, you can not determine what numbers you multiplied or what the final multiplied number is. This is not a fully homomorphic system as it only allows multiplication, but it is a existence proof that you can do operations on ciphertext that apply to the plaintext without being able to recover the plaintext unless you can break the encryption directly.
- mswphd 2mo ago
  conceptually your example is fine/good, but it's worth clarifying that the scheme you describe is insecure, as unpadded RSA fails to be IND-CPA secure. this is because Enc(m)Enc(m') = Enc(mm') is a predicate a passive observer can check, to gain information about Enc(m*m'). that being said, you can construct IND-CPA secure homomorphic encryption schemes from factoring-based assumptions iirc, so this isn't a fundamental obstacle.

by filup 2mo ago

pluto_modadic 2mo ago

they could have gone with an oblivious transfer approach (where it's working on what looks like multiple problems at once, you don't know which)

drdeca 2mo ago

Eh? With secret sharing one can do computation on a shared secret where it is provable that no individual party can recover any information about the data with their share alone. I don’t see why you conclude that FHE couldn’t be close to as secure as that. (Like, not information theoretically, but with computationally bounded adversaries.)

filup 2mo ago
I'm not saying that you can't design a system for secure cloud computing.
- drdeca 2mo ago
  You said that FHE is an oxymoron, seemingly on the basis that in proper encryption the ciphertext is indistinguishable from noise, and you think this can’t be true of FHE. I am arguing to the contrary. In the secret sharing multi-party computation schemes, the individual shares of the secret are random and have no information about the plaintext. I see no reason that FHE can’t have ciphertexts indistinguishable from noise.

Ar-Curunir 2mo ago

No, that’s not what proper encryption means. Security for encryption means that cipher texts encrypting distinct messages are indistinguishable. This is called IND-CPA, and FHE satisfies this.

filup 2mo ago
How can it possibly pass indcpa. If the model can give me any valuable information about the cipher. Apparently the middle man would know precisely what is contained in the payload.
- drdeca 2mo ago
  Here’s a very simple one-time-pad style construction for homeomorphic (but not fully homeomorphic) encryption. Suppose the plaintext, ciphertext, and key, are each a natural number modulo 5. The key is selected uniformly at random. The ciphertext is obtained by adding the key to the plaintext (and as a result is also uniform random). Then the ciphertext is sent to the server. The server only has the ciphertext, which is uniform random. The server then adds some integer mod 5 to the ciphertext, producing a new ciphertext, and sends it back to the user. The user then subtracts their key from the new ciphertext to obtain the new plaintext, which is their original plaintext plus the number the server added. At no point in this process did the server learn anything about the user’s plaintext. This is clearly secure. It is also useless, because just adding a number isn’t a useful thing for a server to do (they may as well just send the user the number and let them add it themselves), but that’s because it is a toy example. I suppose if mind uploading were possible, then under FHE it would in principle be possible to take the ciphertext and run the computation of “this mind upload of this person reads the data and provides some output”, and then presumably that uploaded person would have the experience of seeing the plaintext? But it wouldn’t be possible to get any information about the plaintext without the key (or enough brute force to find the key, but that’s why we use big enough keys to make this infeasible).
  - filup 2mo ago
    What does that have to do with incpa? I send this server a question encrypted. It stays encrypted yet the server distinguished my ciphertext enough to produce a coherent reply. That means there was enough information in the ciphertext for the server to perform the inference, even if it was obscured to where it looks indistinguishable, it apparently wasn't. This doesn't remove trust from the equation, it puts the trust directly on the algorithm. Probably one no one can explain to me like I'm 5. But because it's encrypted I am no longer breaking the law by processing on protected data. I imagine very large contracts await on the other side. Lots of money to be made.

flambo 2mo ago

This is actually the magic of FHE. The ciphertext is indistinguishable from noise AND can be computed on, it just looks like different noise. If you believe the underlying cryptographic hardness assumption of LWE/RLWE/etc, then yes Google cannot see any of the input or output of the model.

filup 2mo ago
If it only appears indistinguishable from noise, but it's actually not, then it's just deception.
- drdeca 2mo ago
  They didn’t say that it “appears” indistinguishable from noise, but that it is indistinguishable. It seems like you strongly believe otherwise, but I suspect you don’t have a good reason to, and just find it unbelievable. Do you think you can distinguish it from noise, if given an implementation and the information an adversary would have access to? Of course, you not being able to wouldn’t demonstrate that noöne can. But, it seems like if you had a good reason to believe that an adversary can, that would suggest you might have some idea of how they could do so. And, if you do have such an idea, then, if that idea works, it would be important for others to know, and if it doesn’t, it would presumably benefit your understanding to see why it doesn’t.
  - filup 2mo ago
    >They didn’t say that it “appears” indistinguishable from noise, but that it is indistinguishable. That's the oxymoron. If it was indistinguishable nothing could be gained. It's not about me being able to distinguish it. It's the model provider saying they cant, when they can.

Veserv 2mo ago

You are objectively wrong. The math is straightforward to show that you can operate on a ciphertext securely in some cryptosystems. Consider two integers M1 and M2. Consider RSA with private key (E), public key (D), and public modulus (N). Encrypt(M, E, N) = mod(pow(M, E), N). Decrypt(C, D, N) = mod(pow(C, D), N). mod(Encrypt(M1, E, N) * Encrypt(M2, E, N), N) = mod(Encrypt(M1 * M2, E, N), N). So, for all RSA encryption, multiplying the ciphertexts results in a ciphertext that is the multiple of the plaintexts. However, unless you can break RSA, you can not determine what numbers you multiplied or what the final multiplied number is. This is not a fully homomorphic system as it only allows multiplication, but it is a existence proof that you can do operations on ciphertext that apply to the plaintext without being able to recover the plaintext unless you can break the encryption directly.

mswphd 2mo ago
conceptually your example is fine/good, but it's worth clarifying that the scheme you describe is insecure, as unpadded RSA fails to be IND-CPA secure. this is because Enc(m)Enc(m') = Enc(mm') is a predicate a passive observer can check, to gain information about Enc(m*m'). that being said, you can construct IND-CPA secure homomorphic encryption schemes from factoring-based assumptions iirc, so this isn't a fundamental obstacle.