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.<p>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).<p>If program obfuscation is related to homomorphic encryption, does the impossibility proof of "black box obfuscators" say anything about that multiplication problem?<p>[0] <a href="http://link.springer.com/chapter/10.1007%2F3-540-44647-8_1" rel="nofollow">http://link.springer.com/chapter/10.1007%2F3-540-44647-8_1</a><p>edit: thanks tptacek, the previous discussion suggests that this is would be a more ambitious result than "mere" homomorphic encryption.
Okay, let's calm down. While the result is great, this article does a pretty bad job describing it. "Could" is pretty darn important in the title. We're nowhere near applications here. For those not willing to read the papers, the original Quanta article[1] is better.<p>I'm flagging this because it's so horribly editorialized.<p>[1] <a href="https://www.simonsfoundation.org/quanta/20140130-perfecting-the-art-of-sensible-nonsense/" rel="nofollow">https://www.simonsfoundation.org/quanta/20140130-perfecting-...</a>
I don't understand, at all. If two programs are semantically equivalent then traditional deobfuscation techniques like symbolic execution, constant propagation + folding, dead code removal, etc. should take you pretty far. Throw in some peephole and pattern based rules specifically targeting this obfuscator and you're good to go.<p>The main link is pretty shit so I may be missing something important. I plan to read the other links provided when I have time, but feel free to help me out by explaining how wrong I am, if that's the case.
For those interested in a simple introduction to Zero Knowledge Proofs, check out: <a href="http://pages.cs.wisc.edu/~mkowalcz/628.pdf" rel="nofollow">http://pages.cs.wisc.edu/~mkowalcz/628.pdf</a>