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∈\bitsetn→\bitsetn) 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 Ω(n/log3(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.