Quick links

Opening the Black-Box: New Techniques in Cryptography

Date and Time
Monday, May 10, 2004 - 10:30am to 12:00pm
Computer Science Small Auditorium (Room 105)
Boaz Barak, from Institute for Advanced Study
Sanjeev Arora
The American Heritage dictionary defines the term "Black-Box" as

"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.

Follow us: Facebook Twitter Linkedin