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 <InlineEquation ID="IEq1"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10207_2025_995_Article_IEq1.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="21" /> </InlineMediaObject> <EquationSource Format="TEX">$2^R$</EquationSource> <EquationSource Format="MATHML"><math> <msup> <mn>2</mn> <mi>R</mi> </msup> </math></EquationSource> </InlineEquation> 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 <InlineEquation ID="IEq2"> <InlineMediaObject> <ImageObject Color="BlackWhite" FileRef="10207_2025_995_Article_IEq2.gif" Format="GIF" Height="17" Rendition="HTML" Resolution="72" Type="Linedraw" Width="75" /> </InlineMediaObject> <EquationSource Format="TEX">$R = 7, 8, 9$</EquationSource> <EquationSource Format="MATHML"><math> <mrow> <mi>R</mi> <mo>=</mo> <mn>7</mn> <mo>,</mo> <mn>8</mn> <mo>,</mo> <mn>9</mn> </mrow> </math></EquationSource> </InlineEquation> 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.

Pseudorandom bit generation with asymmetric numeral systems

期刊论文
出版模式：

开放获取
发表日期：

2025年2月21日

查看全文

Josef Pieprzyk,
Marcin Pawłowski,
Paweł Morawiecki,
Arash Mahboubi,
Jarek Duda,
Seyit Camtepe

摘要

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$ $2^{R}$ 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$ $R = 7, 8, 9$ 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.