2004 | OriginalPaper | Buchkapitel
Notions of Reducibility between Cryptographic Primitives
verfasst von : Omer Reingold, Luca Trevisan, Salil Vadhan
Erschienen in: Theory of Cryptography
Verlag: Springer Berlin Heidelberg
Enthalten in: Professional Book Archive
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Starting with the seminal paper of Impagliazzo and Rudich [17], 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.