Lower bounds on the efficiency of encryption and digital signature schemes Export

@inproceedings{citeulike:3785536, 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 \&\#960; (i.e., no adversary of size S can invert \&\#960; 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 \&\#960; at least \&\#937;(m log S) times. Any private-key encryption scheme for m-bit messages (with k-bit keys) must query \&\#960; at least \&\#937;(m-k/log S) times. Any signature verification algorithm for m-bit messages must query \&\#960; at least \&\#937;(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.}, address = {New York, NY, USA}, author = {Gennaro, Rosario and Gertner, Yael and Katz, Jonathan}, booktitle = {STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing}, citeulike-article-id = {3785536}, citeulike-linkout-0 = {http://portal.acm.org/citation.cfm?id=780542.780604}, citeulike-linkout-1 = {http://dx.doi.org/10.1145/780542.780604}, doi = {10.1145/780542.780604}, isbn = {1-58113-674-9}, keywords = {foundations, lower-bounds}, location = {San Diego, CA, USA}, pages = {417--425}, posted-at = {2008-12-13 14:42:35}, priority = {2}, publisher = {ACM}, title = {Lower bounds on the efficiency of encryption and digital signature schemes}, url = {http://dx.doi.org/10.1145/780542.780604}, year = {2003} }

TY - CONF ID - citeulike:3785536 L3 - citeulike-article-id:3785536 N2 - 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. CY - San Diego, CA, USA SN - 1-58113-674-9 AD - New York, NY, USA EP - 425 TI - Lower bounds on the efficiency of encryption and digital signature schemes PB - ACM T2 - STOC '03: Proceedings of the thirty-fifth annual ACM symposium on Theory of computing SP - 417 KW - foundations KW - lower-bounds AU - Gennaro, Rosario AU - Gertner, Yael AU - Katz, Jonathan PY - 2003/// UR - http://dx.doi.org/10.1145/780542.780604 ER -