Summary: 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 constructions 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 R. Impagliazzo and S. Rudich [Lect. Not. Comput. Sci. 403, 8–26 (1990; Zbl 0718.68042)] and improve and extend earlier results of J. H. Kim, D. R. Simon and P. Tetali [IEEE Symposium 40, 535–542 (1999)]. 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 \(\neq\) NP.