Paper 2011/504

From Non-Adaptive to Adaptive Pseudorandom Functions

Iftach Haitner and Itay Berman

Abstract

Unlike the standard notion of pseudorandom functions (PRF), a non-adaptive PRF is only required to be indistinguishable from a random function in the eyes of a non-adaptive distinguisher (i.e., one that prepares its oracle calls in advance). A recent line of research has studied the possibility of a direct construction of adaptive PRFs from non-adaptive ones, where direct means that the constructed adaptive PRF uses only few (ideally, constant number of) calls to the underlying non-adaptive PRF. Unfortunately, this study has only yielded negative results, showing that ``natural" such constructions are unlikely to exist (e.g., Myers [EUROCRYPT '04], Pietrzak05 [CRYPTO '05, EUROCRYPT '06]). We give an affirmative answer to the above question, presenting a direct construction of adaptive PRFs from non-adaptive ones. The suggested construction is extremely simple, a composition of the non-adaptive PRF with an appropriate pairwise independent hash function.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. TCC 2012 proceedings
Keywords
Adaptive Pseudoerandom functionsComposition
Contact author(s)
iftachh @ cs tau ac il
itayberm @ post tau ac il
History
2012-01-11: revised
2011-09-18: received
See all versions
Short URL
https://ia.cr/2011/504
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2011/504,
      author = {Iftach Haitner and Itay Berman},
      title = {From Non-Adaptive to Adaptive Pseudorandom Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2011/504},
      year = {2011},
      note = {\url{https://eprint.iacr.org/2011/504}},
      url = {https://eprint.iacr.org/2011/504}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.