ECCC-Report TR12-173https://eccc.weizmann.ac.il/report/2012/173Comments and Revisions published for TR12-173en-usSun, 09 Dec 2012 10:21:45 +0200
Paper TR12-173
| A Cookbook for Black-Box Separations and a Recipe for UOWHFs |
Kfir Barhum,
Thomas Holenstein
https://eccc.weizmann.ac.il/report/2012/173We 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.Sun, 09 Dec 2012 10:21:45 +0200https://eccc.weizmann.ac.il/report/2012/173