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 $\mathcal{F}$ and a
parametrized oracle (i.e., an oracle that is defined for every $f \in \{0,1\}^n
\rightarrow \{0,1\}^n$)
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(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 to a recent construction
of Barhum and Maurer.