| Abstract | A central focus of modern cryptography is the construction of efficient, “high-level”cryptographic tools (e.g., encryption schemes) from weaker, “low-level” cryptographic
primitives (e.g., one-way functions). Of interest are both the existence of such construc-
tions, and their efficiency.
Here, we show essentially-tight lower bounds on the best possible efficiency of any
black-box construction of some fundamental cryptographic tools from the most basic
and widely-used cryptographic primitives. Our results hold in an extension of the
model introduced by Impagliazzo and Rudich, and improve and extend earlier results
of Kim, Simon, and Tetali. We focus on constructions of pseudorandom generators,
universal one-way hash functions, and digital signatures based on one-way permutations,
as well as constructions of public- and private-key encryption schemes based on trapdoor
permutations. In each case, we show that any black-box construction beating our
efficiency bound would yield the unconditional existence of a one-way function and
thus, in particular, prove P \= NP
|
