[RTV04] Notions of Reducibility between Cryptographic Primitives

Authors: Omer Reingold, Luca Trevisan, Salil Vadhan | Venue: TCC 2004 | Source

Abstract

Starting with the seminal paper of Impagliazzo and Rudich, there has been a growing body of evidence suggesting that certain cryptographic primitives cannot be reduced to each other via “black-box” reductions. We formalize and unify several notions of black-box reductions between cryptographic primitives, organized along two axes: (1) whether the construction is black-box in the primitive used, and (2) whether the security proof is black-box in the adversary. This framework yields a fine-grained partial order over cryptographic primitives and provides a systematic methodology for proving separations via oracle constructions.