Lower Bounds on the Efficiency of Generic Cryptographic Constructions

Rosario Gennaro; Luca Trevisan

Paper 2000/017

Lower Bounds on the Efficiency of Generic Cryptographic Constructions

Rosario Gennaro and Luca Trevisan

Abstract

We present lower bounds on the efficiency of constructions for Pseudo-Random Generators (PRGs) and Universal One-Way Hash Functions (UOWHFs) based on black-box access to one-way permutations. Our lower bounds are tight as they match the efficiency of known constructions. A PRG (resp. UOWHF) construction based on black-box access is a machine that is given oracle access to a permutation. Whenever the permutation is hard to invert, the construction is hard to break. In this paper we give lower bounds on the number of invocations to the oracle by the construction. If is the assumed security of the oracle permutation (i.e. no adversary of size can invert on a fraction larger than of its inputs) then a PRG (resp. UOWHF) construction that stretches (resp. compresses) its input by bits must query in points. This matches known constructions. Our results are given in an extension of the Impagliazzo-Rudich model. That is, we prove that a proof of the existence of PRG (resp. UOWHF) black-box constructions that beat our lower bound would imply a proof of the unconditional existence of such construction (which would also imply ).

Metadata

Available format(s): PDF PS
Category: Foundations
Publication info: Published elsewhere. Unknown where it was published
Keywords: complexity theory one-way functions pseudo-randomness hash functions lower bounds
Contact author(s): rosario @ watson ibm com
History: 2000-05-02: received
Short URL: https://ia.cr/2000/017
License: CC BY

BibTeX

@misc{cryptoeprint:2000/017,
      author = {Rosario Gennaro and Luca Trevisan},
      title = {Lower Bounds on the Efficiency of Generic Cryptographic Constructions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2000/017},
      year = {2000},
      url = {https://eprint.iacr.org/2000/017}
}