DIMACS TR: 2002-22

Bounds on the Efficiency of Encryption and Digital Signatures

Authors: Rosario Gennaro, Yael Gertner and Jonathan Katz


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 some ``strong'' algorithm (e.g., a private-key encryption scheme) proceeds by giving an explicit construction of the latter from the former. Beyond merely showing such a construction, an equally important research direction is to explore the efficiency of the construction. One might argue that this line of research has become even more important now that minimal assumptions are known for many (but not all) algorithms of interest.

Protocols for encryption (in both the public- and private-key setting) and for digital signatures are fundamental to cryptography. In this work, we show the first lower bounds on the efficiency of constructions of these protocols based on black-box access to one-way or trapdoor one-way permutations. If $S$ is the assumed security of the permutation $\pi$ (i.e., no adversary of size $S$ can ``break'' $\pi$ in the appropriate sense on a fraction larger than $1/S$ of its inputs), our results show that:

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.

Paper Available at: ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2002/2002-22.ps.gz

DIMACS Home Page