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
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. 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:
- Software Obfuscation:
Informally speaking, an obfuscator is a
compiler that takes a program P as input and produces a new
program P' that has the same functionality as P, and yet is
``unintelligible'' in some sense. Ideally, a software obfuscator
should ensure that the only information leaked about P from the
program P', is information that can be derived by using only
black-box access to P. Obfuscators, if they exist, would have a
wide variety of cryptographic and complexity-theoretic
applications, ranging from software protection to homomorphic
encryption to complexity-theoretic analogues of Rice's theorem.
In this thesis, we discuss how to formally define obfuscators, and
whether or not such objects exist. Our main result in this context
is that even very weak forms of obfuscators do not exist.
- Zero-Knowledge:
The simulation paradigm, introduced by
Goldwasser, Micali and Rackoff, has had fundamental impact on
cryptography. A simulator is an algorithm that tries to simulate
the interaction of the adversary with an honest party, without
knowing the private input of this honest party. Loosely speaking,
the existence of such a simulator demonstrates that the adversary
did not gain any knowledge about the honest party's input.
Almost all previously known simulators use the adversary's
algorithm as a black-box. We present the first constructions of
non-black-box simulators. Using these new non-black-box techniques
we obtain several results that were previously shown to be
impossible to obtain using black-box simulators.
Specifically, assuming the existence of collision-resistant hash
functions, we construct a new constant-round zero-knowledge
argument system for NP that satisfies the following properties:
- It remains zero knowledge even when composed concurrently
n times, where n is the security parameter.
- It is an Arthur-Merlin (public coins) protocol.
- It has a simulator that runs in strict polynomial time,
rather than in expected polynomial time.
It is impossible to obtain a constant-round zero-knowledge
protocol satisfying either Property (a) or Property (b) using
black-box simulation (Canetti et al., 2001), (Goldreich and
Krawczyk, 1996). We show that it is also impossible to obtain a
constant-round zero-knowledge protocol satisfying Property (c)
using black-box simulation.
We use this protocol to obtain other new results in cryptography.
These include a construction of constant-round zero-knowledge
proof of knowledge with a strict polynomial-time knowledge
extractor, and a zero-knowledge resettably sound argument for NP.
We show that both applications are impossible to obtain when
restricted to black-box techniques.
- Non-Malleability:
We construct the first constant round
non-malleable commitment scheme and the first constant-round
non-malleable zero-knowledge argument system, as defined by Dolev,
Dwork and Naor. Previous constructions either used a non-constant
number of rounds, or were only secure under stronger setup
assumptions (such as the availability of a public string that was
chosen at random and published by a trusted third party).
We obtain this result by using a non-black-box proof of security.
That is, our proof uses the code of the adversary in the security
reduction.
As an intermediate step we define and construct a constant-round
non-malleable coin tossing protocol. This coin-tossing protocol
may be of independent interest.
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.