[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.

BibTeX

Copy

@Inproceedings{TCC:ReiTreVad04,
  author = {Omer Reingold and Luca Trevisan and Salil P. Vadhan},
  title = {Notions of Reducibility between Cryptographic Primitives},
  pages = {1--20},
  editor = {Moni Naor},
  booktitle = {TCC~2004: 1st Theory of Cryptography Conference},
  volume = {2951},
  series = {Lecture Notes in Computer Science},
  address = {Cambridge, MA, USA},
  month = {feb~19--21},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2004},
  doi = {10.1007/978-3-540-24638-1_1},
}