Cryptology ePrint Archive: Report 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).

Category / Keywords: foundations / Pseudorandom functions, black-box separations, foundations

Original Publication (with major differences): 12th Conference on Security and Cryptography for Networks, SCN 2020

Date: received 6 Sep 2020

Contact author: pratik_soni at cs ucsb edu

Available format(s): PDF | BibTeX Citation

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

Version: 20200909:064508 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]