DIMACS TR: 2002-22
Bounds on the Efficiency of Encryption and Digital Signatures
Authors: Rosario Gennaro, Yael Gertner and Jonathan Katz
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 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:
- Any public-key encryption algorithm for $m$-bit messages must query
$\pi$ at least $\Omega(m/\log S)$ times. This matches the known upper
bound.
- Any private-key encryption algorithm for $m$-bit messages which uses
a $k$-bit key must query $\pi$ at least $\Omega(\frac{m-k}{\log S})$
times. This matches the known upper bound.
- Any signature verification algorithm for $m$-bit messages must query
$\pi$ at least $\Omega(m/\log S)$ times.
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