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

Pratik Soni; Stefano Tessaro

Paper 2020/1075

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

Pratik Soni and Stefano Tessaro

Abstract

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.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published elsewhere. Major revision. 12th Conference on Security and Cryptography for Networks, SCN 2020
DOI: 10.1007/978-3-030-57990-6_27
Keywords: Pseudorandom functions black-box separations foundations
Contact author(s): pratik_soni @ cs ucsb edu
History: 2020-09-09: received
Short URL: https://ia.cr/2020/1075
License: CC BY

BibTeX

@misc{cryptoeprint:2020/1075,
      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},
      url = {https://eprint.iacr.org/2020/1075}
}