|
Abstract : |
A central focus of modern cryptography is the construction of e#cient, "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 also their e#ciency. Here, we show essentially-tight lower bounds on the best possible e#ciency that can be achieved by any black-box construction of some fundamental cryptographic tools from the most basic and widely-used cryptographic primitives. Our results concern constructions of pseudorandom generators, universal one-way hash functions, privatekey encryption schemes, and digital signatures based on one-way permutations, as well as constructions of public-key encryption schemes based on trapdoor permutations. Our proofs are in the model introduced by Impagliazzo and Rudich: in each case, we show that any black-box construction beating our e#ciency bound would yield the unconditional existence of a one-way function and thus, in particular, prove P, |
