Opening the Black-Box: New Techniques in Cryptography

"A device or theoretical construct with known or specified performance characteristics but unknown or unspecified constituents and means of operation."

In the context of Computer Science, to use a program as a black box means to use only its input/output relation by executing the program on chosen inputs, without examining the actual code (i.e., representation as a sequence of symbols) of the program. Using programs as black boxes is very popular in Computer Science, as understanding properties of a program from its code is a notoriously hard problem.

In this talk I will survey some results regarding black-box vs. non-black-box use of programs in cryptography. Somewhat surprisingly and un-intuitively, it turns out that in some cases looking at the code of the program can actually help.

On the positive side, I will present a new cryptographic scheme (a zero knowledge proof system) obtainable using such "non-black-box" techniques. Such a scheme was previously proven not to be obtainable using black-box techniques, and hence was conjectured not to exist. I will also briefly survey other positive applications of "non-black-box" techniques.

I will also demonstrate the power of "non black box" techniques in a negative result, namely an impossibility result for the task of "scrambling" or "obfuscating" software.