## Boaz Barak## From CryptoDox, The Online Encyclopedia on Cryptography and Information SecurityProfessor On Slashdot[2], Barak is most famous for the paper he co-authored,
That paper attempts to define "obfuscate", and gives specific examples of programs that cannot be obfuscated. Because those programs exist, "a general-purpose algorithm for obfuscating any program" does not exist. (This is similar to the fact that "a general-purpose algorithm for determining whether a subroutine halts or runs forever" does not exist, because there exists one (hypothetical) subroutine that no one can determine whether it halts or not. This is the halting problem). The Slashdot discussion mentions
"a paper called The "halting problem" is no longer a practical problem, because we now have techniques ("structured programming") for building subroutines in ways that are guaranteed to eventually halt. Do analogous techniques exist for building subroutines in ways that are guaranteed to be obfuscatable? It still appears to be an open question. |