Boaz Barak

Abstract of PhD Thesis (Weizmann Inst., 2003)

Title: Non-Black-Box Techniques in Cryptography

Available: the thesis (in PSfile). [in PDF].

The American Heritage dictionary defines Black-Box as

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.

Since learning properties of a program from its code is a notoriously hard problem, in most cases both in applied and theoretical computer science, only black-box techniques are used. In fact, there are specific cases in which it has been either proved (e.g., the Halting Problem) or is widely conjectured (e.g., the Satisfiability Problem) that there is no advantage for non-black-box techniques over black-box techniques.

In this thesis, we consider several settings in cryptography, and ask whether there actually is an advantage in using non-black-box techniques over black-box techniques in these settings. Our answer is mainly positive. That is, we show that in several contexts in cryptography, there is a difference between the power of black-box and non-black-box techniques. Using non-black-box techniques we are able to solve some problems in cryptography that were previously unsolved. In fact, some of these problems were previously proven to be unsolvable using black-box techniques.

The main results of this thesis are the following:

To summarize, in this thesis we show that, somewhat unintuitively, non-black-box techniques sometimes have a significant advantage over black-box techniques in cryptography. From the point of view of cryptographers, this result has both negative and positive applications. On the one hand, it further stresses the point that it is unsafe to rely on the assumption that an adversary attacking our schemes will use only black-box techniques. On the other hand, it means that when designing and analyzing cryptographic schemes, we can use these non-black-box techniques to obtain useful and important security goals that cannot be obtained using black-box techniques.

Submitted to the Feinberg Graduate School of the Weizmann Institute of Science, January 2004.

Winner of the ACM Doctoral Dissertation Award, 2004.

Available: the thesis (in PSfile).

Back to Oded Goldreich's homepage.