Instantiating the Hash-then-evaluate paradigm: Strengthening PRFs, PCFs, and OPRFs

Area of Science:

• Cryptography and Information Security
• Theoretical Computer Science
• Applied Mathematics

Background:

• The hash-then-evaluate paradigm is crucial for building pseudorandom functions (PRFs) from weaker primitives.
• Existing constructions often rely on public pre-processing random oracles (ROs), which can be computationally intensive.
• Secure multiparty computation (MPC) applications benefit from PRFs where only low-complexity weak PRFs (wPRFs) handle secret-dependent operations.

Purpose of the Study:

• To instantiate the hash-then-evaluate paradigm for PRFs using a public key and a non-adaptive PRF instead of a random oracle.
• To analyze the security of existing weak PRF candidates when their inputs are generated by this new public pre-processing method.
• To extend these results to oblivious PRFs and pseudorandom correlation functions (PCFs).

Main Methods:

• Replaced the random oracle (RO) in the PRF construction with a function `f(k_H, elf(x))`, where `f` is a non-adaptive PRF and `k_H` is a public key.
• Performed cryptanalysis analogous to existing methods, leveraging the pseudorandomness of `f` to ensure good statistical properties.
• Investigated the implications of attacks on wPRFs with pseudorandom inputs for cryptographic assumptions like the Learning Parity with Noise (LPN) problem.

Main Results:

• Demonstrated that several existing weak PRF candidates remain plausibly secure under the new construction.
• Showed that an attack on a wPRF with pseudorandom inputs generated by `f` could imply key agreement from the hardness of high-noise LPN.
• Successfully applied the transformation to obtain results for oblivious PRFs and PCFs, core components for PAKE, PSI, and silent OT extension.

Conclusions:

• The proposed transformation of replacing RO pre-processing with public `f(k_H, elf(x))` pre-processing is effective and broadly applicable.
• This approach maintains security while potentially reducing computational complexity in MPC and related cryptographic protocols.
• The findings provide new constructions for essential cryptographic primitives like oblivious PRFs and PCFs.