@conference {15146, title = {Lower bounds on the efficiency of encryption and digital signature schemes}, booktitle = {Proceedings of the thirty-fifth annual ACM symposium on Theory of computing}, series = {STOC {\textquoteright}03}, year = {2003}, month = {2003///}, pages = {417 - 425}, publisher = {ACM}, organization = {ACM}, address = {New York, NY, USA}, 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/S 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.}, keywords = {black-box, digital signatures, encryption, lower bounds}, isbn = {1-58113-674-9}, doi = {10.1145/780542.780604}, url = {http://doi.acm.org/10.1145/780542.780604}, author = {Gennaro,Rosario and Gertner,Yael and Katz, Jonathan} }