Notions of Reducibility
between Cryptographic Primitives
Omer Reingold, Luca Trevisan, and Salil Vadhan
Abstract
Starting with the seminal paper of Impagliazzo and Rudich [IR89], there has been a
large body of work showing that various cryptographic primitives cannot be reduced to each
other via ``black-box'' reductions. The common interpretation of these results is that there are inherent limitations in using
a primitive as a black box, and that these impossibility results can be overcome only by
explicitly using the code of the primitive in the construction.
In this paper we revisit these negative results, give a more careful taxonomy of the ways in which
"black-box reductions" can be formalized, strengthen some previous results (in particular
giving unconditional impossibility results for reductions that were previously only shown to imply
P != NP), and offer a new interpretation of them: in many cases, there is no limitation in
using a primitive as a black box, but there is a limitation in treating
adversaries as such. In particular, these negative results may be overcome by using the
code of the adversary in the analysis.
Versions
-
In Proceedings of the First Theory of Cryptography Conference (TCC `04),
volume 2951 of Lecture Notes in Computer Science, pages 1-20. Springer-Verlag,
19-21 February 2004. [postscript][pdf][official
Springer page]
[
back to Salil Vadhan's research]