Counter-based random number generator explained

A counter-based random number generation (CBRNG, also known as a counter-based pseudo-random number generator, or CBPRNG) is a kind of pseudorandom number generator that uses only an integer counter as its internal state. They are generally used for generating pseudorandom numbers for large parallel computations.

Background

We can think of a pseudorandom number generator (PRNG) as a function that transforms a series of bits known as the state into a new state and a random number.

That is, given a PRNG function and an initial state

state _{0} , we can repeatedly use the PRNG to generate a sequence of states and random numbers.

In some PRNGs, such as the Mersenne Twister, the state is large, more than 2048 bytes. In other PRNGs, such as xorshift,

state _{i} and num _{i} are one and the same (and so the state is small, just 4, 8, or 16 bytes, depending on the size of the numbers being generated). But in both cases, and indeed in most traditional PRNGs, the state evolves unpredictably, so if you want to calculate a particular state _{i} given an initial state state _{0} , you have to calculate state _{1} , state _{2} , and so on, running the PRNG i times.

Such algorithms are inherently sequential and not amenable to running on parallel machines like multi-core CPUs and GPUs.

In contrast, a counter-based random number generator (CBRNG) is a PRNG where the state "evolves" in a particularly simple manner:

state _{i} = i . This way you can generate each number independently, without knowing the result of the previous call to the PRNG.

This property make it easy to run a CBRNG on a multiple CPU threads or a GPU. For example, to generate

n random numbers on a GPU, you might spawn n threads and have the i th thread calculate PRNG (i) .

CBRNGs based on block ciphers

Some CBRNGs are based on reduced-strength versions of block ciphers. Below we explain how this works.

When using a cryptographic block cipher in counter mode, you generate a series of blocks of random bits. The

i th block is calculated by encrypting the number i using the encryption key k : Block _{i} = E(i, k) .

This is similar to a CBRNG, where you calculate the

i th random number as PRNG (i) . Indeed, any block cipher can be used as a CBRNG; simply let PRNG (i) = E(i, seed ) !

This yields a strong, cryptographically-secure source of randomness. But cryptographically-secure pseudorandom number generators tend to be slow compared to insecure PRNGs, and in practice many uses of random numbers don't require this degree of security.

In 2011, Salmon et al. at D. E. Shaw Research introduced^[1] two CBRNGs based on reduced-strength versions of block ciphers.

• Threefry uses a reduced-strength version of the Threefish block cipher. (Juvenile fish are known as "fry".)
• ARS uses a reduced-strength version of the AES block cipher. ("ARS" is a pun on "AES"; "AES" stands for "advanced encryption standard", and "ARS" stands for "advanced randomization system"^[2]).

ARS is used in recent versions of Intel's Math Kernel Library^[3] and gets good performance by using instructions from the AES-NI instruction set, which specifically accelerate AES encryption.

Code implementing Threefry, ARS, and Philox (see below) is available from the authors.^[4]

CBRNGs based on multiplication

In addition to Threefry and ARS, Salmon et al. described a third counter-based PRNG, Philox, based on wide multiplies; e.g. multiplying two 32-bit numbers and producing a 64-bit number, or multiplying two 64-bit numbers and producing a 128-bit number.

As of 2020, Philox is popular on CPUs and GPUs. On GPUs, nVidia's library^[5] and TensorFlow^[6] provide implementations of Philox. On CPUs, Intel's MKL provides an implementation.

A new CBRNG based on multiplication is the Squares RNG.^[7] This generator passes stringent tests of randomness^[8] and is considerably faster than Philox.

Notes and References

1. Parallel random numbers: as easy as 1, 2, 3. Salmon. John. 2011. Proceedings of 2011 International Conference for High Performance Computing, Networking, Storage and Analysis, Article No. 16. 10.1145/2063384.2063405. Moraes. Mark. Dror. Ron. Shaw. David.
2. Web site: Random123: A Library of Counter-Based Random Number Generators. August 8, 2020.
3. Web site: New counter-based Random Number Generators in Intel® Math Kernel Library . Fedorov . Gennady . Gladkov . Eugeny . 2015 . Intel . August 22, 2016.
4. Web site: Random123.
5. Web site: Device API Overview. August 8, 2020.
6. Web site: Random number generation | TensorFlow Core.
7. Widynski . Bernard. 2004.06278 . Squares: A Fast Counter-Based RNG. cs.DS . 2020 .
8. Multiple streams with recurrence-based, counter-based, and splittable random number generators. 2021 Winter Simulation Conference (WSC). IEEE, 2021. 2021. L’Ecuyer. Pierre. Nadeau-Chamard . Oliver. Chen. Yi-Fan. Lebar. Justin.