Modern Random Number Generation

Liam Quinn

Image by Robert Stump on Unsplash

Introduction

Random number generators existed long before computers. All civilizations throughout the years have felt the need to produce random selections for a variety of applications. The Romans had a name for the process of flipping a coin to determine a choice between two outcomes: 'navia aut caput', or "boat or heads" [1]. Dice have been found even earlier than this, with examples as far back as 5,000-years old being found in the Middle East. Random number generation has since advanced past simple rolling of dice or shuffling of cards. It is an even more critical part of our society than ever before. This article will describe random numbers, how to generate them, and how we can test whether sequences are genuinely random.

What are Random Numbers, and Why are they Important?

Random number generation describes a system that produces a sequence of numbers for which the next value in the sequence cannot be predicted more reliably than by guesswork. The output sequence may contain detectable patterns in hindsight, but they cannot contain patterns that are more or less likely in the future. Observing heads on a coin flip 10 times in a row does not necessarily mean that the next toss is more likely to be a heads again for example. A good random number generator makes values that are entirely independent of all previous numbers. Rolling a dice would be a poor example, as minor imperfections and the initial position of the dice in your hand will affect the final output value. Rolling dice is also a poor choice because it is too slow for practical uses.

The need for random numbers arises in many applications today. One application is the simulation of physical models, such as in Condensed Matter or Solid-state physics [2, 3]. Monte Carlo simulation methods for studying lattices and fluid mechanics is one example of this [4]. Possibly the most widespread use is in the field of cryptography, which underpins security in modern communications [3, 5,6]. Other areas of interest include banking, gambling and statistical sampling [7, 8]. Cryptography requires a secure random number generator (RNG) for cryptographic keys and communications, and the use of imperfect RNG's can have severe consequences. The predictability of a random number generator to any extent can lead to a backdoor which an attacker can use to break the encryption [9]. For example, this year's blockchain-based platform Poly Network was attacked in early August of this year, with over $600 million in various cryptocurrencies stolen, highlighting the need for secure network processes.

Random numbers generated using computer algorithms as shown above can never be regarded as truly random. Image by Markus Spiske on Unsplash.

‘True’ Random Numbers

Random numbers generated using computer algorithms as shown above can never be regarded as truly random. Image by Markus Spiske on Unsplash.

There are two main methods for generating chains of random numbers. The first uses a physical phenomenon that is known to be random. The most common example of these hardware random number generators uses thermal noise [10]. By measuring random fluctuations in the temperature, we can generate a string of numbers that is, in theory, random. The problem with these methods is that the devices used to measure the randomness often themselves have asymmetries and biases that compromise the randomness [11]. Random number generators based on quantum effects can, to some extent, bypass these limitations and are a leading technique for RNG's [12, 13, 14, 15, 16]. In quantum mechanics, a system can be prepared in a superposition of two states — like Schrodinger’s cat being both alive and dead at the same time. According to Born's rule, the measurement outcome of such a prepared state is intrinsically random. Therefore, in theory, quantum measurements can be used to generate genuinely random numbers [18,19].

The second and more common method uses computer algorithms to generate long strings of numbers that appear to be random. A much shorter series of numbers known as a key is fed into a pseudo-random number generator and determines the values of the output chain. The problem with this method is that it is still deterministic; the entire sequence can be reconstructed if the initial key is known. This type of generator is called a pseudo-random number generator (PRNG) and is what your calculator or computer uses to simulate randomness [5, 17]. PRNG's cannot be regarded as 'true' random number generators. However, they are sufficient for most applications. For example, computer games use pseudo-random number generators, as they are fast and easy to implement. More complicated PRNG's are used by coding languages such as Python, and these generators are often well suited for numerical modelling.

Due to the innate predictability of PRNG data streams, they are potentially vulnerable to cryptanalysis — the process of attempting to breach cryptographic security systems even without the initial key. For this reason, hardware random number generators can be a powerful tool, as the ideal system will be genuinely random. The lack of predictability is the main reason the field of hardware random number generators remains such a large area of research, even though PRNG's are faster, easier and simpler to implement.

Testing Randomness

The big question now is this: if we have a stream of random numbers, how can we test if they are random? The answer is to perform a series of statistical tests that tell us how unusual the observed result was. For the following discussion, we will consider a stream of numbers that only take on the values '1' or '0'. Each of these results is, in theory, independent of each other, and future outputs are unpredictable.

The NIST Statistical Test Suite for Random Number Generation lays out in great detail 15 tests that can determine if a stream of numbers appear to be random or not [17]. Each of these tests will return a probability that the result could be observed under the assumption that the data is random (the null hypothesis). This probability is known as a p-value. A low p-value implies that it is unlikely that the source of data is truly random.

The low hanging fruit for a test of randomness is the monobit test. This test compares the total number of '1's and '0's observed. If you were tossing a coin to make decisions and landed on heads 100 times and tails 20, you would probably want to get a new coin. We choose to use a threshold of 1/100, which means any event that is more unlikely than 1 in 100 is considered to provide evidence against randomness. To see how this would work with quantification, the bit chain 1011010101 has a p-value of 0.527 for this test. There is, therefore, no evidence under this test that the chain is non-random. On the other hand, a chain of 1111101111 has a p-value of 0.004. Observing a chain, this 'unusual' would happen around 1 time out of every 250 under the assumption that the data source is genuinely random, so we would say that we have evidence to suggest that the data is not random.

The monobit test is the most straightforward test used to measure this randomness, and there are many other tests in use. They can measure anything from the expected runs (the number of times a number occurs in a row) to testing if specific patterns come up more or less than expected. In order to truly test the randomness of an RNG source, however, it is best to use millions of data points to spot any very weak patterns throughout the data. If '0' appears an extra time every 1000 numbers, it will generally take at the very least several thousand numbers tested in order to find this weak source of non-randomness.

Using Polarised Laser Light to Generate Random Numbers

There are many exciting future technologies for hardware random number generation. Methods that rely on quantum effects as their source of randomness remain the most exciting area of research due to the 'pureness' of the quantum process. This purity is limited by the quality of experimental setups however.

One potential source of quantum randomness is polarised light, which has led to the work I have completed with my colleague Gang Xu under the supervision of Miro Erkintalo and Stephane Coen. We generate millions of random numbers every second using pulses of laser light in a resonator.

The figure above shows the results from several hundred numerical simulations highlighting how once we cross a threshold, there becomes two possible states that the laser light can exist in. These states are chosen at random.

By pumping light into a loop of optical fibre, we can achieve high intensities inside the cavity. Under these high powers, nonlinear effects start to come into play, whereby the effect of the fibre on the light depends on the intensity of the light itself. These nonlinear effects are what allow us to create the random number generation [20].

The figure above shows the results from several hundred numerical simulations highlighting how once we cross a threshold, there becomes two possible states that the laser light can exist in. These states are chosen at random.

The crucial part of our specific design is that light within the cavity can exist in either one of two states (called polarisation modes). At low enough pump strengths, we find that these two polarisation modes will have identical intensities and are perfectly balanced. However, as we slowly increase the power in the system, we find that the two polarizations’ intensities can no longer be the same, and the system undergoes a bifurcation [21, 22]. This means that one of the polarizations must have a high intensity, while the other mode has a low intensity.

As these modes are initially identical; which one ends up with the high or low intensity is entirely random, thus leading to the generation of random numbers. We can randomly generate a 0 (low intensity) or a 1 (high intensity) by measuring only one polarisation mode as the bifurcation occurs.

We can generate a new set of random bits by resetting the system and increasing the power again. As light moves at literally a billion kilometres an hour, we can repeat this process very rapidly, allowing us to generate several million bits per second.

One nice aspect of this setup is that the dynamics of our system have a two-round trip periodicity. What this means in practical terms is that any imperfections in our system get averaged out. If the x-polarisation is favoured in one roundtrip of light, in the next, the y-polarisation will be favoured instead. Therefore, asymmetries or biases are automatically averaged out in our setup, and the random selection of a high intensity and a low-intensity polarisation mode is genuinely random.

Figure 2: Experimental data obtained by measuring the intensity of one polarisation mode. Each spike represents a single light pulse in a high or low intensity state.

Conclusion

Random number generation is an integral part of our society, whether we are aware of it or not. This process is essential to global security, and the need for secure random number generation will only increase with the developments in modern computing and cryptanalysis. Modern hardware random number generators will continue to have great importance in security and numerical modelling as sources of 'true' randomness in years to come.

References

[1] Pierre L'Ecuyer. “History of uniform random number generation.” In 2017 Winter Simulation Conference (WSC), pages 202{230, Las Vegas, NV, December 2017. IEEE.

[2] Alan M. Ferrenberg, Jiahao Xu, and David P. Landau. “Pushing the limits of Monte Carlo simulations for the three-dimensional Ising model.” Physical Review E, 97(4):043301, 2018.

[3] Toni Stojanovski and Ljupco Kocarev. “Chaos-based random number generators-part I: Analysis [cryptography].” IEEE Transactions on Circuits and Systems I: Fundamental Theory and Applications, 48(3):281{288, 2001.

[4] A Baumgartner et. al, “The Monte Carlo method in condensed matter physics,” (71), 2012

[5] Melissa O'Neill. “PCG: A Family of Simple Fast Space-Ecient Statistically Good Algorithms or Random Number Generation.” page 58.

[6] Gwangmin Kim, Jae Hyun In, Young Seok Kim, Hakseung Rhee, Woojoon Park, Hanchan Song, Juseong Park, and Kyung Min Kim. “Self-clocking fast and variation tolerant true random number generator based on a stochastic mott memristor.” Nature Communications, 12(1):2906, May 2021.

[7] Adam Levinthal and Michael Barnett. “The Silicon Gaming Odyssey Slot Machine.” In Proceedings IEEE COMPCON 97. Digest of Papers, pages 296{301. IEEE, 1997.

[8] Ralf Korn, Elke Korn, and Gerald Kroisandt. “Monte Carlo Methods and Models in Finance and Insurance.” CRC press, 2010.

[9] Matthew Green. “The Many Flaws of Dual EC DRBG,” September 2013.

[10] Cheng Wu, Bing Bai, Yang Liu, Xiaoming Zhang, Meng Yang, Yuan Cao, Jianfeng Wang, Shaohua Zhang, Hongyan Zhou, Xiheng Shi, Xiongfeng Ma, Ji-Gang Ren, Jun Zhang, Cheng-Zhi Peng, Jingyun Fan, Qiang Zhang, and Jian-Wei Pan. “Random Number Generation with Cosmic Photons.” Physical Review Letters, 118(14):140402, April 2017.

[11] Pierre L'ecuyer. “Ecient and portable combined random number generators.” Communications of the ACM, 31(6):742{751, 1988.

[12] Christian Gabriel, Christofer Wittmann, Denis Sych, Ruifang Dong, Wolfgang Mauerer, Ulrik L. Andersen, Christoph Marquardt, and Gerd Leuchs. “A generator for unique quantum random numbers based on vacuum states.” Nature Photonics, 4(10):711{715, October 2010.

[13] Tommaso Lunghi, Jonatan Bohr Brask, Charles CiWen Lim, Quentin Lavigne, Joseph Bowles, Anthony Martin, Hugo Zbinden, and Nicolas Brunner. “Self-Testing Quantum Random Number Generator.” Physical Review Letters, 114(15):150501, April 2015.

[14] Yoshitomo Okawachi, Mengjie Yu, Kevin Luke, Daniel O. Carvalho, Michal Lipson, and Alexander L. Gaeta. “Quantum random number generator using a microresonator-based Kerr oscillator.” Optics Letters, 41(18):4194, September 2016.

[15] Bruno Sanguinetti, Anthony Martin, Hugo Zbinden, and Nicolas Gisin. “Quantum Random Number Generation on a Mobile Phone.” Physical Review X, 4(3):031056, September 2014.

[16] Yanbao Zhang, Hsin-Pin Lo, Alan Mink, Takuya Ikuta, Toshimori Honjo, Hiroki Takesue, and William J. Munro. “A simple low-latency real-time certiable quantum random number generator.” Nature Communications, 12(1):1056, December 2021.

[17] Andrew Rukhin, Juan Soto, James Nechvatal, Elaine Barker, Stefan Leigh, Mark Levenson, David Banks, Alan Heckert, and James Dray. “A Statistical Test Suite for Random and Pseudorandom Number Generators for Cryptographic Applications.” page 131.

[18] J. E. Jacak, W. A. Jacak, W. A. Donderowicz, and L. Jacak, “Quantum random number generators with entanglement for public randomness testing," Scientic Reports, vol. 10, no. 1,p. 164, Jan. 2020.

[19] X. Ma, X. Yuan, Z. Cao, B. Qi, and Z. Zhang, “Quantum random number generation," npj Quantum Information, vol. 2, no. 1, pp. 19, Jun. 2016.

[20] S. Coen and M. Erkintalo, “Temporal Cavity Solitons in Kerr Media," in Nonlinear Optical Cavity Dynamics, P. Grelu, Ed. Weinheim, Germany: Wiley-VCH Verlag GmbH & Co. KGaA, Dec. 2015, pp. 11{40.

[21] J. Fatome, G. Xu, B. Garbin, N. Berti, G.-L. Oppo, S. G. Murdoch, M. Erkintalo, and S. Coen, “Self-symmetrization of symmetry-breaking dynamics in passive Kerr resonators," p. 13.

[22] B. Garbin, J. Fatome, G.-L. Oppo, M. Erkintalo, S. G. Murdoch, and S. Coen, “Asymmetric balance in symmetry breaking," Physical Review Research, vol. 2, no. 2, p. 023244, May 2020.