4 ms·

The article isn't about FHE, it's about iO. As you point out there's no reduction from FHE to iO, but there is one going the other way. Worth noting though that

The article isn't about FHE, it's about iO. As you point out there's no reduction from FHE to iO, but there is one going the other way. Worth noting though that when Boaz et al wrote that paper, even FHE wasn't known to exist. As for the iO result, not sure whether you were saying you thought the result wasn't solid because of the Boaz paper, but my understanding from people in the field is that it's expected to hold up and of course Boaz is quoted in the article.

sillysaurusx 6y ago
Can someone break down in simple terms what the difference is between FHE and iO? What can you do with FHE that you can’t do with iO? A concrete example would help tremendously. I always mentally substituted FHE with “the ability to encrypt a function such that no attacker can reverse engineer how that function was implemented,” i.e. “input go in, output go brr.” Crucially, in FHE this is true even if you yourself are the one executing the program and can observe everything the program is doing. Or... in whatever I thought FHE was.
- KenoFischer 6y ago
  In FHE, you need some sort of key to decrypt the result. In obfuscation the result comes out clear text. General obfuscation is impossible, but iO gives you basically the best possible result which is "given any method of computing the same function (for some complexity parameter of the function in question) you will always be able learn at least as much from said method as from the obfuscated function" (in other words iO gives you a circuit that is as hard to reverse engineer as the hardest circuit of a given size that computes the same function, but it doesn't give you a guarantee on how hard that actually is).
  - sillysaurusx 6y ago
    Suppose I have a function which returns input + 42. I wish to obfuscate that function so that no one can determine how I arrived at the result, even if they themselves are executing the program. In simple terms, why is FHE different from iO? I’ve read your reply a few times, but I don’t understand the concrete distinction. What is the “best possible result” of input + 42 obfuscatabiliry? Note that I am using + 42 as a trivial example; please mentally substitute with “for example, a bunch of matrix operations to compute a super secret formula result.”
    - KenoFischer 6y ago
      You can use FHE to encrypt functions, but the more standard use is to encrypt inputs and evaluate plain text functions (e.g. in a two part sort of protocol, see e.g. [1]). Regardless, the important difference to obfuscation is that once you're done computing, the output from FHE will still be encrypted. Somebody has to have a key to decrypt that and that key can most likely also be used to decrypt the function. In iO, the result comes out plain text. [1] https://juliacomputing.com/blog/2019/11/encrypted-machine-learning/ https://juliacomputing.com/blog/2019/11/encrypted-machine-le...
    - aruss 6y ago
      Former crypto PhD student here. Here's the formal definition. FHE means that, given an encryption Enc(x) of plaintext x, you can compute Enc(f(x)). Note that without the decryption key, Enc(f(x)) is just as "useless" as Enc(x) (i.e., it looks totally random). FHE would be useful if you wanted Google to filter all of your emails for spam, but didn't want them reading your emails. Google would receive Enc(email) and compute Enc(isSpam(email)) and then forward Enc(email) and Enc(isSpam(email)) to your email client, which would then decrypt both and either send `email` to spam or not. Note that in this scenario, Google learns nothing about `email`, not even if it is spam or not. Here's what iO means: given two different circuits C_0 and C_1 that both compute a function f, the obfuscations iO(C_0) and iO(C_1) are indistinguishable (to a polytime adversary). In the email example, you could have a circuit C that computes isSpam over encrypted emails, but with a decrypted result. That is, C(Enc(email)) = isSpam(email). But note that this leaks information to Google, and the security definition of iO does NOT guarantee that Google does not learn anything about your secret key (the obfuscation might not hide the secret key at all). Definitionally, they're very, very different things and have very different security guarantees. The weird thing about iO is that the security definition doesn't immediately appear to actually secure much, so it doesn't seem very useful. However, it turns out that iO is an incredibly powerful primitive because it can be combined with other things like pseudorandom generators to build up a lot of other primitives. For example, you can combine secret-key encryption and iO to get public-key encryption in a very elegant way.
  - sterlind 6y ago
    Can you use iO to decrypt an FHE ciphertext and return an obfuscated output only if the ciphertext matches some value? The iO circuit would need the FHE decryption key and the hidden output. If there were exactly one FHE ciphertext for any plaintext (which can't work, otherwise you could distinguish FHE values and break it), then you could simply implement this by supplying <target FHE ciphertext> XOR <obfuscated secret>. Is there a scheme where iO could do this, or is it impossible because any obfuscation would necessarily require both the FHE decryption key and the obfuscated secret?
- pqoek 6y ago
  FHE: - I encrypt data Encrypt(key, data) = ciphertext1 - you operate on encrypted data f(ciphertext1) = ciphertext2 - I decrypt the result to obtain Decrypt(key, ciphertext2) = f(data) for iO it's more like: I give you the algorithm to encrypt your data: some_algorithm(data) = Encrypt(key, data) but you can't figure out what "key" is, even though you have the code and it's not some remote service
  - aruss 6y ago
    iO doesn't guarantee that the adversary can't figure out what "key" is. It turns out that this is possible, but it requires some very careful applications of a special kind of pseudorandom generator.

sillysaurusx 6y ago

Can someone break down in simple terms what the difference is between FHE and iO? What can you do with FHE that you can’t do with iO? A concrete example would help tremendously. I always mentally substituted FHE with “the ability to encrypt a function such that no attacker can reverse engineer how that function was implemented,” i.e. “input go in, output go brr.” Crucially, in FHE this is true even if you yourself are the one executing the program and can observe everything the program is doing. Or... in whatever I thought FHE was.

KenoFischer 6y ago
In FHE, you need some sort of key to decrypt the result. In obfuscation the result comes out clear text. General obfuscation is impossible, but iO gives you basically the best possible result which is "given any method of computing the same function (for some complexity parameter of the function in question) you will always be able learn at least as much from said method as from the obfuscated function" (in other words iO gives you a circuit that is as hard to reverse engineer as the hardest circuit of a given size that computes the same function, but it doesn't give you a guarantee on how hard that actually is).
- sillysaurusx 6y ago
  Suppose I have a function which returns input + 42. I wish to obfuscate that function so that no one can determine how I arrived at the result, even if they themselves are executing the program. In simple terms, why is FHE different from iO? I’ve read your reply a few times, but I don’t understand the concrete distinction. What is the “best possible result” of input + 42 obfuscatabiliry? Note that I am using + 42 as a trivial example; please mentally substitute with “for example, a bunch of matrix operations to compute a super secret formula result.”
  - KenoFischer 6y ago
    You can use FHE to encrypt functions, but the more standard use is to encrypt inputs and evaluate plain text functions (e.g. in a two part sort of protocol, see e.g. [1]). Regardless, the important difference to obfuscation is that once you're done computing, the output from FHE will still be encrypted. Somebody has to have a key to decrypt that and that key can most likely also be used to decrypt the function. In iO, the result comes out plain text. [1] https://juliacomputing.com/blog/2019/11/encrypted-machine-learning/ https://juliacomputing.com/blog/2019/11/encrypted-machine-le...
  - aruss 6y ago
    Former crypto PhD student here. Here's the formal definition. FHE means that, given an encryption Enc(x) of plaintext x, you can compute Enc(f(x)). Note that without the decryption key, Enc(f(x)) is just as "useless" as Enc(x) (i.e., it looks totally random). FHE would be useful if you wanted Google to filter all of your emails for spam, but didn't want them reading your emails. Google would receive Enc(email) and compute Enc(isSpam(email)) and then forward Enc(email) and Enc(isSpam(email)) to your email client, which would then decrypt both and either send `email` to spam or not. Note that in this scenario, Google learns nothing about `email`, not even if it is spam or not. Here's what iO means: given two different circuits C_0 and C_1 that both compute a function f, the obfuscations iO(C_0) and iO(C_1) are indistinguishable (to a polytime adversary). In the email example, you could have a circuit C that computes isSpam over encrypted emails, but with a decrypted result. That is, C(Enc(email)) = isSpam(email). But note that this leaks information to Google, and the security definition of iO does NOT guarantee that Google does not learn anything about your secret key (the obfuscation might not hide the secret key at all). Definitionally, they're very, very different things and have very different security guarantees. The weird thing about iO is that the security definition doesn't immediately appear to actually secure much, so it doesn't seem very useful. However, it turns out that iO is an incredibly powerful primitive because it can be combined with other things like pseudorandom generators to build up a lot of other primitives. For example, you can combine secret-key encryption and iO to get public-key encryption in a very elegant way.
- sterlind 6y ago
  Can you use iO to decrypt an FHE ciphertext and return an obfuscated output only if the ciphertext matches some value? The iO circuit would need the FHE decryption key and the hidden output. If there were exactly one FHE ciphertext for any plaintext (which can't work, otherwise you could distinguish FHE values and break it), then you could simply implement this by supplying <target FHE ciphertext> XOR <obfuscated secret>. Is there a scheme where iO could do this, or is it impossible because any obfuscation would necessarily require both the FHE decryption key and the obfuscated secret?
pqoek 6y ago
FHE: - I encrypt data Encrypt(key, data) = ciphertext1 - you operate on encrypted data f(ciphertext1) = ciphertext2 - I decrypt the result to obtain Decrypt(key, ciphertext2) = f(data) for iO it's more like: I give you the algorithm to encrypt your data: some_algorithm(data) = Encrypt(key, data) but you can't figure out what "key" is, even though you have the code and it's not some remote service
- aruss 6y ago
  iO doesn't guarantee that the adversary can't figure out what "key" is. It turns out that this is possible, but it requires some very careful applications of a special kind of pseudorandom generator.