Paper 2013/101

Notions of Black-Box Reductions, Revisited

Paul Baecher, Chris Brzuska, and Marc Fischlin


Reductions are the common technique to prove security of cryptographic constructions based on a primitive. They take an allegedly successful adversary against the construction and turn it into a successful adversary against the underlying primitive. To a large extent, these reductions are black-box in the sense that they consider the primitive and/or the adversary against the construction only via the input-output behavior, but do not depend on internals like the code of the primitive or of the adversary. Reingold, Trevisan, and Vadhan~(TCC, 2004) provided a widely adopted framework, called the RTV framework from hereon, to classify and relate different notions of black-box reductions. Having precise notions for such reductions is very important when it comes to black-box separations, where one shows that black-box reductions cannot exist. An impossibility result, which clearly specifies the type of reduction it rules out, enables us to identify the potential leverages to bypass the separation. We acknowledge this by extending the RTV framework in several respects using a more fine-grained approach. First, we capture a type of reduction---frequently ruled out by so-called meta-reductions---which escapes the RTV framework so far. Second, we consider notions that are ``almost black-box'', i.e., where the reduction receives additional information about the adversary, such as its success probability. Third, we distinguish explicitly between efficient and inefficient primitives and adversaries, allowing us to determine how relativizing reductions in the sense of Impagliazzo and Rudich (STOC, 1989) fit into the picture.

Available format(s)
Publication info
A major revision of an IACR publication in ASIACRYPT 2013
Foundationsblack-box reductionsblack-box separations.
Contact author(s)
pbaecher @ gmail com
2013-11-29: last of 2 revisions
2013-02-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Paul Baecher and Chris Brzuska and Marc Fischlin},
      title = {Notions of Black-Box Reductions, Revisited},
      howpublished = {Cryptology ePrint Archive, Paper 2013/101},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.