Paper 2022/005

Pseudorandom Bit Generation with Asymmetric Numeral Systems

Josef Pieprzyk, Marcin Pawlowski, Pawel Morawiecki, Arash Mahboubi, Jarek Duda, and Seyit Camtepe


The generation of pseudorandom binary sequences is of a great importance in numerous applications stretching from simulation and gambling to cryptography. Pseudorandom bit generators (PRBGs) can be split into two classes depending on their claimed security. The first includes PRBGs that are provably secure (such as the Blum-Blum-Shub one). Security of the second class rests on heuristic arguments. Sadly, PRBG from the first class are inherently inefficient and some PRBG are insecure against quantum attacks. While, their siblings from the second class are very efficient, but security relies on their resistance against known cryptographic attacks. This work presents a construction of PRBG from the asymmetric numeral system (ANS) compression algorithm. We define a family of PRBGs for $2^R$ ANS states and prove that it is indistinguishable from a truly random one for a big enough $R$. To make our construction efficient, we investigate PRBG built for smaller $R=7,8,9$ and show how to remove local correlations from output stream. We permute output bits using rotation and Keccak transformations and show that permuted bits pass all NIST tests. Our PRBG design is provably secure (for a large enough $R$) and heuristically secure (for a smaller $R$). Besides, we claim that our PRBG is secure against quantum adversaries.

Available format(s)
Secret-key cryptography
Publication info
Preprint. MINOR revision.
PseudorandomnessEntropy EncodingCompressionAsymmetric Numeral SystemsIndistinguishabilityANSPRBGPRNGKeccak
Contact author(s)
josef pieprzyk @ gmail com
2022-01-07: received
Short URL
Creative Commons Attribution


      author = {Josef Pieprzyk and Marcin Pawlowski and Pawel Morawiecki and Arash Mahboubi and Jarek Duda and Seyit Camtepe},
      title = {Pseudorandom Bit Generation with Asymmetric Numeral Systems},
      howpublished = {Cryptology ePrint Archive, Paper 2022/005},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.