A TPRF-based pseudo-random number generator

Abstract

Most cryptographic applications use randomness that is generated by pseudo-random number generators (PRNGs). A popular PRNG practical choice is the NIST standardized CTR_DRBG. In their recent ACNS 2023 publication, Andreeva and Weninger proposed a new and more efficient and secure PRNG called FCRNG. FCRNG is based on CTR_DRBG and uses the 𝑛-to-2𝑛 forkcipher expanding primitive ForkSkinny as a building block. In this work, we create a new BKRNG PRNG, which is based on FCRNG and employs the novel 𝑛-to-8𝑛 expanding primitive Butterknife. Butterknife is based on the Deoxys tweakable blockcipher (and thus AES) and realizes a tweakable expanding pseudo-random function. While both blockciphers and forkciphers are invertible primitives, tweakable expanding pseudo-random functions are not. This functional simplification enables security benefits for BKRNG in the robustness security game - the standard security goal for a PRNG. Contrary to the security bound of CTR_DRBG, we show that the security of our BKRNG construction does not degrade with the length of the random inputs, nor the number of requested output pseudo-random bits. We also empirically verify the BKRNG security with the NIST PRNG test suite and the TestU01 suite. Furthermore, we show the 𝑛-to-8𝑛 multi-branch expanding nature of Butterknife contributes to a significant speed-up in the efficiency of BKRNG compared to FCRNG. More concretely, producing random bits with BKRNG is 30.0% faster than FCRNG and 49.2% faster than CTR_DRBG.