| Abstract | A central focus of modern cryptography is to investigate the weakest possible assumptionsunder which various cryptographic algorithms exist. Typically, a proof that a “weak” prim-
itive (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 π (i.e., no
adversary of size S can “break” π 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 π at least Ω(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 π at least Ω(m−k
logS
) times. This matches the known upper bound.
• Any signature verification algorithm for m-bit messages must query π at least Ω(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.
|
