Pseudorandom bit generation with asymmetric numeral systems

Abstract The generation of pseudorandom binary sequences is of great importance in numerous applications, ranging from simulation and gambling to cryptography. Pseudorandom bit generators (PRBGs) can be divided into two categories based on their claimed security. The first category includes PRBGs that are provably secure, such as the Blum–Blum–Shub generator. The security of the second category relies on heuristic arguments. Unfortunately, PRBGs from the first category are inherently inefficient, and some are vulnerable to quantum attacks. In contrast, those in the second category are highly efficient, though their security depends on their resistance to known cryptographic attacks. This work presents a construction of a PRBG based on the asymmetric numeral system (ANS) compression algorithm. We define a family of PRBGs for $$2^R$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:msup> <mml:mn>2</mml:mn> <mml:mi>R</mml:mi> </mml:msup> </mml:math> ANS states and prove that it is indistinguishable from a truly random generator for sufficiently large R . To enhance efficiency, we explore PRBGs with smaller values of $$R = 7, 8, 9$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mi>R</mml:mi> <mml:mo>=</mml:mo> <mml:mn>7</mml:mn> <mml:mo>,</mml:mo> <mml:mn>8</mml:mn> <mml:mo>,</mml:mo> <mml:mn>9</mml:mn> </mml:mrow> </mml:math> and demonstrate methods for removing local correlations in the output stream. We permute output bits using rotation and Keccak transformations, showing that the permuted bits pass all NIST tests. Our PRBG design is provably secure for large values of R and heuristically secure for smaller values. Additionally, we claim that our PRBG is secure against quantum adversaries.