4 ms·

Fully homomorphic encryption?! Reads article Yup! Gosh, I can't wait for it to become remotely practical. It's been a few years -- wow, almost a decade -- bu

Fully homomorphic encryption?! Reads article Yup! Gosh, I can't wait for it to become remotely practical. It's been a few years -- wow, almost a decade -- but I remember a paper that claimed to prove that "no fully homomorphic program can be written such that the secret key was guarded in all cases," i.e. it's theoretically possible to trick a FHE program into giving up its own key, unless your program is basically trivial. It was one of those papers that you run across, then never see again, and wistfully wish you'd saved a reference to. Tantalizing idea, if true, but probably not true. EDIT: I just went back to finish the article, and they linked to it: https://link.springer.com/chapter/10.1007/3-540-44647-8_1 https://link.springer.com/chapter/10.1007/3-540-44647-8_1 Welp. Looks like it was a good paper!

hacknat 6y ago
Reading the abstract of the "paper" (book) that you linked it looks like what they are attempting to prove is that there are classes of functions in which obfuscation is impossible. My guess is that iO could still be attempted by simply guarding against these certain classes (which may even be difficult to create in the real world). However, that book does look daunting. I am curious if the book hints at more potential problems than the abstract indicates.
- sillysaurusx 6y ago
  Unlocked paper: https://moscow.sci-hub.se/2256/6ffcc08f6e40c37f84b5287edf9a57bb/barak2001.pdf https://moscow.sci-hub.se/2256/6ffcc08f6e40c37f84b5287edf9a5... I wish I had endless free time. It would be so, so fun to dive into this. Because you’re right — I got the sense that there were more potential problems than was previously appreciated. It would be fascinating to know exactly what problems there are, and whether they’re fundamental problems or “dodgeable.”
bawolff 6y ago
I haven't fully absorbed this, but isn't this kind of the opposite of FHE? In FHE you are hiding the input and output. Here you are hiding the function (or in the PHFE application the function and part of the input)
- sillysaurusx 6y ago
  Hmm. I thought “fully homomorphic encryption” == “hiding the function,” not merely input and output. Have I been using that term incorrectly? It’s possible. If so, what’s the canonical acronym for “encrypting a function”?
  - feanaro 6y ago
    FHE is the ability to encrypt some data and give it to a machine, which is then able to perform sensible operations on it without decrypting it (and thus ever learning the plaintext). The term you are looking for is "obfuscation". Either black-box obfuscation (which was shown to be impossible) or the indistinguishability obfuscation, which is what the article talks about.
  - aruss 6y ago
    You can encrypt a function with FHE, but the applications of that are limited because the output is encrypted as well. We've had provably secure FHE since Gentry's 2009 paper. Obfuscation roughly means "encrypting a function." But here be dragons: since the adversary gets non-black-box access to the implementation of the function (a circuit), and can also learn as many (input, output = f(input)) pairs as they want, it becomes impossible to say that the adversary cannot learn anything else about f in the general case (intuitively, consider a higher-order function f: you could learn a lot about f by computing f(f)).
KenoFischer 6y ago
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.”

hacknat 6y ago

Reading the abstract of the "paper" (book) that you linked it looks like what they are attempting to prove is that there are classes of functions in which obfuscation is impossible. My guess is that iO could still be attempted by simply guarding against these certain classes (which may even be difficult to create in the real world). However, that book does look daunting. I am curious if the book hints at more potential problems than the abstract indicates.

sillysaurusx 6y ago
Unlocked paper: https://moscow.sci-hub.se/2256/6ffcc08f6e40c37f84b5287edf9a57bb/barak2001.pdf https://moscow.sci-hub.se/2256/6ffcc08f6e40c37f84b5287edf9a5... I wish I had endless free time. It would be so, so fun to dive into this. Because you’re right — I got the sense that there were more potential problems than was previously appreciated. It would be fascinating to know exactly what problems there are, and whether they’re fundamental problems or “dodgeable.”

bawolff 6y ago

I haven't fully absorbed this, but isn't this kind of the opposite of FHE? In FHE you are hiding the input and output. Here you are hiding the function (or in the PHFE application the function and part of the input)

sillysaurusx 6y ago
Hmm. I thought “fully homomorphic encryption” == “hiding the function,” not merely input and output. Have I been using that term incorrectly? It’s possible. If so, what’s the canonical acronym for “encrypting a function”?
- feanaro 6y ago
  FHE is the ability to encrypt some data and give it to a machine, which is then able to perform sensible operations on it without decrypting it (and thus ever learning the plaintext). The term you are looking for is "obfuscation". Either black-box obfuscation (which was shown to be impossible) or the indistinguishability obfuscation, which is what the article talks about.
- aruss 6y ago
  You can encrypt a function with FHE, but the applications of that are limited because the output is encrypted as well. We've had provably secure FHE since Gentry's 2009 paper. Obfuscation roughly means "encrypting a function." But here be dragons: since the adversary gets non-black-box access to the implementation of the function (a circuit), and can also learn as many (input, output = f(input)) pairs as they want, it becomes impossible to say that the adversary cannot learn anything else about f in the general case (intuitively, consider a higher-order function f: you could learn a lot about f by computing f(f)).

KenoFischer 6y ago

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