[MM11] On Black-Box Separations among Injective One-Way Functions

Authors: Takahiro Matsuda, Kanta Matsuura | Venue: TCC 2011 | Source

Abstract

A one-way permutation (OWP) is one of the most fundamental cryptographic primitives, and can be used as a building block for most of basic symmetric-key cryptographic primitives. However, despite its importance and usefulness, previous black-box separation results have shown that constructing a OWP from another primitive seems hopeless, unless building blocks already achieve “one-way” property and “permutation” property simultaneously. In this paper, in order to clarify more about the constructions of a OWP from other primitives, we study the construction of a OWP from primitives that are very close to a OWP. Concretely, as a negative result, we show that there is no fully black-box construction of a OWP from a length-increasing injective one-way function (OWF), even if the latter is just 1-bit-increasing and achieves strong form of one-wayness which we call adaptive one-wayness. As a corollary, we show that there is no fully black-box construction of a OWP from a regular OWF with regularity greater than 1. Since a permutation is length-preserving and injective, and is a regular OWF with regularity 1, our negative result indicates that to construct a OWP from another primitive is quite difficult, even if we use very close primitives to a OWP as building blocks. Moreover, we extend our separation result of a OWP from a length-increasing injective OWF, and show a certain restrictive form of black-box separations among injective OWFs in terms of how much a function stretches its input. This result shows a hierarchy among injective OWFs (including a OWP).

BibTeX

Copy

@Inproceedings{TCC:MatMat11,
  author = {Takahiro Matsuda and Kanta Matsuura},
  title = {On Black-Box Separations among Injective One-Way Functions},
  pages = {597--614},
  editor = {Yuval Ishai},
  booktitle = {TCC~2011: 8th Theory of Cryptography Conference},
  volume = {6597},
  series = {Lecture Notes in Computer Science},
  address = {Providence, RI, USA},
  month = {mar~28--30},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2011},
  doi = {10.1007/978-3-642-19571-6_36},
}