Jump to content
Tuts 4 You

Non-Black-Box Techniques in Cryptography

Teddy Rogers

About This File

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.

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. Somewhat surprisingly, 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.

User Feedback

Recommended Comments

There are no comments to display.

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now
  • Create New...