A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion

M.  Bellare; R.  Impagliazzo

Paper 1999/024

A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion

M. Bellare and R. Impagliazzo

Abstract

We present a general probabilistic lemma that can be applied to upper bound the advantage of an adversary in distinguishing between two families of functions. Our lemma reduces the task of upper bounding the advantage to that of upper bounding the ratio of two probabilities associated to the adversary, when this ratio is is viewed as a random variable. It enables us to obtain significantly tighter analyses than more conventional methods. In this paper we apply the technique to the problem of PRP to PRF conversion. We present a simple, new construction of a PRF from a PRP that makes only two invocations of the PRP and has insecurity linear in the number of queries made by the adversary. We also improve the analysis of the truncation construction.

Metadata

Available format(s): PS
Publication info: Published elsewhere. Appeared in the THEORY OF CRYPTOGRAPHY LIBRARY and has been included in the ePrint Archive.
Keywords: Pseudorandom functions pseudorandom permutations provable security birthday attacks.
Contact author(s): russell @ cs ucsd edu
History: 1999-12-12: received
Short URL: https://ia.cr/1999/024
License: CC BY

BibTeX

@misc{cryptoeprint:1999/024,
      author = {M.  Bellare and R.  Impagliazzo},
      title = {A tool for obtaining tighter security analyses of pseudorandom function based constructions, with applications to PRP to PRF conversion},
      howpublished = {Cryptology ePrint Archive, Paper 1999/024},
      year = {1999},
      note = {\url{https://eprint.iacr.org/1999/024}},
      url = {https://eprint.iacr.org/1999/024}
}