TR12-173 Authors: Kfir Barhum, Thomas Holenstein

Publication: 9th December 2012 10:21

Downloads: 3864

Keywords:

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.