Pseudorandom bit generation with asymmetric numeral systems
Open Access
- 21 February 2025
- journal article
- regular contribution
- Published by Springer Nature in International Journal of Information Security
- Vol. 24 (2) , 1-18
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$$ 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$$ 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.
Keywords
Funding Information
- Commonwealth Scientific and Industrial Research Organisation
This publication has 16 references indexed in Scilit:
- Compcrypt–Lightweight ANS-Based Compression and EncryptionIEEE Transactions on Information Forensics and Security, 2021
- Comparative Analysis of Random Generators2020
- Keccak2013
- Obtaining True-Random Binary Numbers from a Weak Radioactive Source2005
- Algebraic Attacks on Stream Ciphers with Linear Feedback2003
- Finite Markov Chains and Algorithmic Applications2002
- Random Graphs2001
- The Magma Algebra System I: The User LanguageJournal of Symbolic Computation, 1997
- Theory and application of trapdoor functions1982
- A Method for the Construction of Minimum-Redundancy CodesProceedings of the IRE, 1952