Instantiating the Hash-Then-Evaluate Paradigm : Strengthening PRFs, PCFs, and OPRFs

We instantiate the hash-then-evaluate paradigm for pseudorandom functions (PRFs), PRF(k,x):=wPRF(k,RO(x)), which builds a PRF PRF from a weak PRF wPRF via a public pre-processing random oracle RO. In applications to secure multiparty computation (MPC), only the low-complexity wPRF performs secret-depending operations. Our construction replaces RO by f(k_H,elf(x)), where f is a non-adaptive PRF and the key k_H is public and thus known to the distinguishing adversary. We show that, perhaps surprisingly, several existing weak PRF candidates are plausibly also secure when their inputs are generated by f(k_H,elf(.)). Firstly, analogous cryptanalysis applies (because pseudorandomness of f implies good statistical properties) and/or secondly an attack against the weak PRF with such pseudorandom inputs generated by f would imply surprising results such as key agreement from the hardness of the high-noise version of the Learning Parity with Noise (LPN) when implementing both wPRF and f from this assumption. Our simple transformation of replacing RO(·) public pre-processing by f(k_H,elf(x)) public pre-processing applies to the entire family of PRF-style functions. Specifically, we obtain results for oblivious PRFs, which are a core building block for password-based authenticated key exchange (PAKE) and private set intersection (PSI) protocols, and we also obtain results for pseudorandom correlation functions (PCF), which are a key tool for silent oblivious transfer (OT) extension.