Lower bounds on the efficiency of encryption and digital signature schemes

Abstract

A central focus of modern cryptography is to investigate the weakest possible assumptions under which various cryptographic algorithms exist. Typically, a proof that a "weak" primitive (e.g., a one-way function) implies the existence of a "strong" algorithm (e.g., a private-key encryption scheme) proceeds by giving an explicit construction of the latter from the former. In addition to showing the existence of such a construction, an equally important research direction is to explore the efficiency of such constructions. Among the most fundamental cryptographic algorithms are digital signature schemes and schemes for public- or private-key encryption. Here, we show the first lower bounds on the efficiency of any encryption or signature construction based on black-box access to one-way or trapdoor one-way permutations. If S is the assumed security of the permutation π (i.e., no adversary of size S can invert π on a fraction larger than 1/5 of its inputs), our results show that: Any public-key encryption scheme for m-bit messages must query π at least Ω(m/log S) times. Any private-key encryption scheme for m-bit messages (with k-bit keys) must query π at least Ω(m-k/log S) times. Any signature verification algorithm for m-bit messages must query π at least Ω(m/log S) times. Our bounds match known upper bounds for the case of encryption. We prove our results in an extension of the Impagliazzo-Rudich model. That is, we show that any black-box construction beating our lower bounds would imply the unconditional existence of a one-way function.