Boaz Barak

From CryptoDox, The Online Encyclopedia on Cryptography and Information Security

Jump to: navigation, search

Professor Boaz Barak teaches cryptography in the CS department of Princeton University. "I am mainly interested in cryptography (especially the foundations of cryptography) and complexity theory." [1]

On Slashdot[2], Barak is most famous for the paper he co-authored,

On the (Im)possibility of Obfuscating Programs, CRYPTO 2001 [3][4] .

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 Protecting Mobile Agents against Malicious Hosts by Tomas Sander and Christian F. Tschudin", which seems to imply that at least some specially-designed programs can be obfuscated. (This is similar to the fact that other specific subroutines can be determined to halt, and some specific subroutines can be determined to run forever.)

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.