3 ms·

The papers are over my head, but they both at least mention homomorphic encryption. As far as I can tell, program obfuscation is a related, but distinct mathema

The papers are over my head, but they both at least mention homomorphic encryption. As far as I can tell, program obfuscation is a related, but distinct mathematical problem. Has anyone read and understood the impossibility proof[0] from 2001 they linked? My lay understanding is that we've got addition tackled for homomorphic encryption, but multiplication eludes us so far (i.e. algebraic groups but not fields). If program obfuscation is related to homomorphic encryption, does the impossibility proof of "black box obfuscators" say anything about that multiplication problem? [0] http://link.springer.com/chapter/10.1007%2F3-540-44647-8_1 http://link.springer.com/chapter/10.1007%2F3-540-44647-8_1 edit: thanks tptacek, the previous discussion suggests that this is would be a more ambitious result than "mere" homomorphic encryption.

pbsd 13y ago
It's obfuscation that is dependent on fully homomorphic encryption (FHE), not the other way around. Therefore, Barak's impossibility proof is irrelevant to FHE. With respect to FHE, before 2009 we already had some tools. We had RSA, which is multiplicatively homomorphic (this property is the reason behind the need for good padding!). We also had Paillier, which is additively homomorphic. We even had Boneh-Goh-Nissim, where you could do any number of additions plus one multiplication! In 2009 Gentry completed the picture with a partially homomorphic system, based on lattices, where you could do a number of additions and multiplications before losing "precision". Perhaps more importantly, he also gave us the bootstrapping notion, which allows you to achieve a fully homomorphic encryption scheme from a partially homomorphic one, provided you have enough "precision". Now, what the article talks about is not strictly covered by Barak's theorem, since it's a different notion (also defined in Barak's paper): indistinguishability obfuscation. Barak proved that black-box obfuscation is impossible in the general case (i.e., for every possible program). Black-box obfuscation is the usual intuitive notion we have of obfuscation: given an obfuscated problem, you can't obtain any more information from it than if you were just querying it as a black-box. Indistinguishability obfuscation is more subtle: given two different programs that compute the same function, you can't tell whether an obfuscated program is the obfuscation of the first or the second one. This at first sounds pretty useless as an obfuscation scheme, since it gives us few guarantees, but the authors took advantage of this notion to get some useful functionality out of it (namely functional encryption, and later other things). Even more impressive is the fact that they now have managed to prove that a variant of the original scheme is actually black-box secure [1]. How is this compatible with Barak's result, you ask? The black-box proof of [1] is in the multilinear model, which means it is under the assumption that the attacker can only do a limited set of (algebraic) operations. A poor analogy would be to show that some code obfuscation scheme is secure, but only as long as the attacker is limited to using static analysis. [1] https://eprint.iacr.org/2013/631 https://eprint.iacr.org/2013/631

pbsd 13y ago

It's obfuscation that is dependent on fully homomorphic encryption (FHE), not the other way around. Therefore, Barak's impossibility proof is irrelevant to FHE. With respect to FHE, before 2009 we already had some tools. We had RSA, which is multiplicatively homomorphic (this property is the reason behind the need for good padding!). We also had Paillier, which is additively homomorphic. We even had Boneh-Goh-Nissim, where you could do any number of additions plus one multiplication! In 2009 Gentry completed the picture with a partially homomorphic system, based on lattices, where you could do a number of additions and multiplications before losing "precision". Perhaps more importantly, he also gave us the bootstrapping notion, which allows you to achieve a fully homomorphic encryption scheme from a partially homomorphic one, provided you have enough "precision". Now, what the article talks about is not strictly covered by Barak's theorem, since it's a different notion (also defined in Barak's paper): indistinguishability obfuscation. Barak proved that black-box obfuscation is impossible in the general case (i.e., for every possible program). Black-box obfuscation is the usual intuitive notion we have of obfuscation: given an obfuscated problem, you can't obtain any more information from it than if you were just querying it as a black-box. Indistinguishability obfuscation is more subtle: given two different programs that compute the same function, you can't tell whether an obfuscated program is the obfuscation of the first or the second one. This at first sounds pretty useless as an obfuscation scheme, since it gives us few guarantees, but the authors took advantage of this notion to get some useful functionality out of it (namely functional encryption, and later other things). Even more impressive is the fact that they now have managed to prove that a variant of the original scheme is actually black-box secure [1]. How is this compatible with Barak's result, you ask? The black-box proof of [1] is in the multilinear model, which means it is under the assumption that the attacker can only do a limited set of (algebraic) operations. A poor analogy would be to show that some code obfuscation scheme is secure, but only as long as the attacker is limited to using static analysis. [1] https://eprint.iacr.org/2013/631 https://eprint.iacr.org/2013/631