Paper 2020/1075

On the Query Complexity of Constructing PRFs from Non-adaptive PRFs

Pratik Soni and Stefano Tessaro


This paper studies constructions of pseudorandom functions (PRFs) from non-adaptive PRFs (naPRFs), i.e., PRFs which are secure only against distinguishers issuing all of their queries at once. Berman and Haitner (Journal of Cryptology, '15) gave a one-call construction which, however, is not hardness preserving -- to obtain a secure PRF (against polynomial-time distinguishers), they need to rely on a naPRF secure against superpolynomial-time distinguishers; in contrast, all known hardness-preserving constructions require $\omega(1)$ calls. This leaves open the question of whether a stronger superpolynomial-time assumption is necessary for one-call (or constant-call) approaches. Here, we show that a large class of one-call constructions (which in particular includes the one of Berman and Haitner) cannot be proved to be a secure PRF under a black-box reduction to the (polynomial-time) naPRF security of the underlying function. Our result complements existing impossibility results (Myers, EUROCRYPT '04; Pietrzak, CRYPTO '05) ruling out natural specific approaches, such as parallel and sequential composition. Furthermore, we show that our techniques extend to rule out a natural class of constructions making parallel but arbitrary number of calls which in particular includes parallel composition and the two-call, cuckoo-hashing based construction of Berman et al.\ (Journal of Cryptology, '19).

Note: This is the full version of the work that appears at SCN 2020.

Available format(s)
Publication info
Published elsewhere. MAJOR revision.12th Conference on Security and Cryptography for Networks, SCN 2020
Pseudorandom functionsblack-box separationsfoundations
Contact author(s)
pratik_soni @ cs ucsb edu
2020-09-09: received
Short URL
Creative Commons Attribution


      author = {Pratik Soni and Stefano Tessaro},
      title = {On the Query Complexity of Constructing PRFs from Non-adaptive PRFs},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1075},
      year = {2020},
      doi = {10.1007/978-3-030-57990-6_27},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.