Learning Burnside Homomorphisms with Rounding and Pseudorandom Function

The use of pseudorandom function (PRF) and weak PRF as foundational primitives is common in a variety of cryptographic applications, including encryption, authentication, and identification. In this paper, we present a new PRF construction derived from a weak PRF family. Specifically, we propose a derandomization technique from a post-quantum hardness assumption known as learning Burnside homomorphisms with noise ( \(B_n\) -LHN). Through the derandomization, a new hardness assumption arises, which we refer to as learning Burnside homomorphisms with rounding ( \(B_n\) -LHR). We establish the security of the derandomization by demonstrating that the \(B_n\) -LHR problem is at least as hard as the \(B_n\) -LHN problem. In the work by Naor and Reingold (NR), a PRF construction is introduced based on a weak PRF family, utilizing a novel cryptographic primitive called a pseudorandom synthesizer (PRS). However, this approach necessitates an excessively large key size to design a PRF family. To overcome this issue and produce a more efficient PRF construction, we design a length-doubling pseudorandom generator (PRG) from a weak PRF. Here, the PRG is defined using the secret-key components of a PRF. Notably, in our PRF construction, the length-doubling PRG exhibits efficiency primarily when employed as an intermediate function. We also provide insight into the \(B_n\) -LHR problem by discussing the details of the concatenation operation and error distribution in the Burnside group.