We present a new framework for proving fully black-box
separations and lower bounds. We prove a general theorem that facilitates
the proofs of fully black-box lower bounds from a one-way function (OWF).
Loosely speaking, our theorem says that in order to prove that a fully black-box
construction does not securely construct a cryptographic primitive $Q$
(e.g., a pseudo-random generator or a universal one-way hash function) from a
OWF, it is enough to come up with a large enough set of functions $\calF$ and a
parameterized oracle (i.e., an oracle that is defined for every $f \in \bitsetn
\rightarrow \bitsetn$) such that $O_{f}$ breaks the security of the
construction when instantiated with $f$ and the oracle satisfies two local
properties.
Our main application of the theorem is a lower bound of $\Omega(n/\log^3(n))$ on
the number of calls made by any fully black-box construction of a universal
one-way hash function (UOWHF) from a general one-way function. The bound holds
even when the OWF is regular, in which case it matches up to a poly-logarithmic
factor to a recent construction of Barhum and Maurer.
Joint work with Thomas Holenstein.