Cryptography and Communications Computer Networks and Communications
Instantiating the Hash-then-evaluate paradigm: Strengthening PRFs, PCFs, and OPRFs
Abstract
Abstract We instantiate the hash-then-evaluate paradigm for pseudorandom functions (PRFs), $$\textsf{PRF}(k,x):=\textsf{wPRF}(k,\textsf{RO}(x))$$ PRF ( k , x ) : = wPRF ( k , RO ( x ) ) , which builds a PRF $$\textsf{PRF}$$ PRF from a weak PRF $$\textsf{wPRF}$$ wPRF via a public pre-processing random oracle $$\textsf{RO}$$ RO . In applications to secure multiparty computation (MPC), only the low-complexity $$\textsf{wPRF}$$ wPRF performs secret-depending operations. Our construction replaces $$\textsf{RO}$$ RO by $$f(k_\textsf{H},\textsf{elf}(x))$$ f ( k H , elf ( x ) ) , where f is a non-adaptive PRF and the key $$k_\textsf{H}$$ 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_\textsf{H},\textsf{elf}(.))$$ 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 $$\textsf{wPRF}$$ wPRF and f from this assumption. Our simple transformation of replacing $$\textsf{RO}(\cdot )$$ RO ( · ) public pre-processing by $$f(k_\textsf{H},\textsf{elf}(x))$$ 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.