We present a new framework for proving fully black-boxseparations and lower bounds. We prove a general theorem that facilitatesthe 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 aOWF, it is enough to come up with a large enough set of functions and aparametrized oracle (i.e., an oracle that is defined for every f01n01n )such that Of 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 (nlog(n)) on the number of calls made by any fully black-box construction of a universalone-way hash function (UOWHF) from a general one-way function. The bound holdseven when the OWF is regular, in which case it matches to a recent constructionof Barhum and Maurer.