Issue |
Emergent Scientist
Volume 1, 2017
International Physicists' Tournament 2016
|
|
---|---|---|
Article Number | 7 | |
Number of page(s) | 4 | |
DOI | https://doi.org/10.1051/emsci/2017009 | |
Published online | 24 October 2017 |
Research Article
A simple quantum generator of random numbers
1
Département de Physique, ENS-PSL Research University, 24 rue Lhomond, 75005 Paris, France
2
Laboratoire Kastler Brossel, ENS-PSL Research University, CNRS, UPMC, Collège de France, 24 rue Lhomond, 75005 Paris, France
* e-mail: hugo.roussille@ens.fr
Received:
10
September
2017
Accepted:
11
September
2017
Cryptography techniques rely on chains of random numbers used to generate safe encryption keys. Since random number generator algorithms are in fact pseudo-random their behavior can be predicted if the generation method is known and as such they cannot be used for perfectly safe communications. In this article, we present a perfectly random generator based on quantum measurement processes. The main advantage of such a generator is that using quantum mechanics, its behavior cannot be predicted in any way. We verify the randomness of our generator and compare it to commonly used pseudo-random generators.
© H. Roussille et al., Published by EDP Sciences, 2017
This is an Open Access article distributed under the terms of the Creative Commons Attribution License (http://creativecommons.org/licenses/by/4.0), which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited.
1 Introduction
With the increasing need of secure online communications, cryptography has become one of the cornerstones of computer science. The security of the communications relies on the strength of the algorithm used: for instance the widely used RSA algorithm is only partially secure since its security is based on the difficulty of factorizing large numbers [1]. On the other hand, encryption algorithms based on random keys provide perfectly safe communication protocols [2]. According to Kerckhoffs’s principle [3], the strength of this class of cryptographic algorithms rely entirely the randomness of the key. If the behavior of the generator can be in any way predicted, so does the key, and as a result the privacy of the communication is compromised. This problem has been studied thoroughly, for example in the case of Windows operating system [4].
Computer generated random sequences are only pseudo-random. They are based on deterministic algorithms and they use the entropy generated by the user’s actions and the computer components to generate randomness. An example of such a pseudo-random number generator (PRNG) is Linux’s/dev/random [5]. The main drawback of this kind of generator is that they can easily loop, or create low-entropy numbers. As a consequence, one must be extra careful when using a PRNG [6]. A possible solution would be to use quantum random numbers generators (QRNGs) [7]. Being based on the intrinsic probabilistic nature of quantum measurements, their main advantage is that they can produce a string which is fundamentally unpredictable, even if the device’s behavior is fully known. QRNGs have been implemented on different experimental platforms, for example using the quantum fluctuations of vacuum [8], parametric oscillators [9], Raman scattering [10, 11] or photon shot-noise [12].
Here, we present a simple quantum randomizer based onthe statistics of arrival times of single photons on an avalanche photodiode. We show that the randomness of the generator is directly related to its bit-rate and that for a single detector, an almost perfectly random chain of 0 and 1 can be obtained for a bit rate of ≃20 bit/s.
2 Principle of the generator
Every number can be written in base 2, and if this number has been chosen randomly, then every bit of its decomposition in base 2 follows a Bernoulli law of parameter 0.5; the reciprocal is also true. Then, to get a random number, we only have to generate random bits.
The principle of our generator relies on the fact that photon emission is an intrinsically quantum process [13]. As a consequence, their emission time is a random quantity which can be used to generate a string of random bits. Let be the times at which photons are detected and let us define (1)
the duration between two subsequent detection events (see Fig. 1). If the photon pairs corresponding to the time intervals dm and dn are independent, we expect to have P (dn > dm) = P (dm > dn). But we have P (dn > dm) + P (dm > dn) + P (dn = dm) = 1 and P (dn = dm) = 0 for we consider continuous probabilities. Thus, if two durations are independent, there is a 1∕2 probability that the first is greater than the second and 1∕2 probability that the second is greater than the first: (2)
From this 1∕2 probability, we can extract easily a bit by defining bn = H (dn − dm) where H is Heaviside’s function. We thus have a sequence of bits bn randomly chosen. However, if n and m are too close, the random variables dn and dm are not independent. These correlations have various origins, from the dead time of the detector that introduces anti-correlation at short-time, to quantum-statistics effect arising fromthe bosonic nature of photons [13].
Fig. 1 Scheme of the durations received (each vertical bar represents a photon). tn is the arrival time of the nth photon and dn = tn+1 − tn. We define a random bit from the sign of dn − dm for sufficiently different values of n and m to avoid correlations between arrival times. |
3 Experimental implementation
The experimental setup is presented in Figure 2. The laser source is a 50 mW laser diode shining a Thorlabs SPCM50A avalanche photodiode (APD). A cardboard tube is placed between them to reduce the dark photon count to 3 photon/s. Data acquisition was performed using a Python program based on the NI Visa Python library.
The achievable photon flux is limited by the bin time duringwhich photon counting is performed and the dead-time separating two bins. To avoid multiple-photon events, we reduced the bin time to 1 μs, leading to less than 1% of multiple events. The dead-time of the detector τ is 19 μs. For a flux comparable or larger than 1∕τ, a significantnumber of photons will not be detected, leading to strong anti-correlations in the statistics of arrival times. To avoid this bias, we reduced the photon flux to 1700 counts/s by inserting two neutral density filters decreasing the beam intensity by a factor 104 and 103 , respectively.Then we made sure the beam was centered on the detector, and used the fact that the beam was much largerthan the detector. The detector was 50 μm wide, and our beam was 30 times wider (radius of 1.5 mm) yielding an intensity reduction by an additional factor 900.
Fig. 2 Upper panel: Picture of the setup. The laser source is a 50 mW laser diode attenuated by two neutral density filters. Photons are detected using an avalanche photo-diode (APD) operated in single-photon counting mode. Lower panel: Example of detection signal. Two separated bins are separated by a 19 μs dead-time. |
4 Experimental results and randomness tests
To obtain a sufficient number of values, we ran our program several times and then concatenated the obtained arrays. Using this sample, we could generate a chain of 2 933 920 bits on which we performed a series of statistical tests to assess the randomness of the sequence.
We first display in Figure 3 the histogram of time intervals dn used to generate the random sequence. It can be fitted by an exponential law, showing that the probability of detection per unit time is constant. This corresponds to a Poissonnian distribution of the times between two emissions. We then estimate the average and the variance of the bn and compare them to the ideal Bernoulli distribution. The experimental average and the variance are respectively 0.49995 and 0.25000. These values are extremely close to those we would theoretically obtain with a probability . To make sure the theoretical value was coherent with our results, we computed the trust intervals at 99.7% and 68% using Student’s coefficients [14]. (3)
Thus, the generator is a compatible with a Bernoulli random variable of parameter 0.5.
To further test the quality of the generator, we estimate first the autocorrelation function of the data defined by (4)
In Figure 4 we plotted the autocorrelation of the first bits. We observe that correlations vanish after the first bins.
To refine the characterization of the random sequence, we run two common statistical tests. Firstly, we use the Monte-Carlo method to estimate the numerical value of π, by randomly sampling points in a unit square. The fraction of points at a distance to the origin lower than 1 is then an approximation of π/4 and any bias in the random sequence translates into a systematic error on the determination of the computed value of π. The result is shown in Figure 5 where we generated the random sequence by comparing dn and dn+i. We can see that the result of the method is acceptably comparable to Python’s random as soon as we take i = 15, which is a sharper condition than the one obtained solely from Figure 4. To be precise, in this case the error produced by our random number generator is around 0.3% and it is comparable to that obtained using Python’s built-in generator.
As a final test, we implemented the birthday spacing test [15], which is a commonly-used process used to test random numbers generators: if random points are chosen on an interval; the spacing between the points should be exponentially distributed (this is the source of the so-called birthday paradox demonstrating our poor grasp of random phenomena). The test generates “birthdays” based on the output of our generator and compares them to the theoretical distribution by computing the chi-square and the associated p-value. If the p-value is greater than 0.05, the test is generally considered has being successful. Just like with the Monte-Carlo test, our generator passed the test when we took only one duration out of 15.
Fig. 3 Histogram of the duration between subsequent arrival times. Dots: experimental data; solid line: time between two emissions for the laser used in our setup. |
Fig. 5 Results of the Monte-Carlo method for the calculation of π using the durations dn and dn+k, where k is the number of ignored events, for the determination of each bit. |
Fig. 4 Autocorrelation function of the random sequence. |
5 Conclusion and outlook
In this article, we have presented a quantum random-number generator based on the arrival time of individual photons on an avalanche photodiode. We have shown that the optimal protocol is the result of a trade-off between the bit-rate and the quality of the random sequence. Based on the outcome of the Monte-Carlo test, the maximum bit-rate allowed by our setup is about 20 bits⋅s-1, for 1700 photons per second photon count. The main limiting factor is probably the dead-time of the APD but further study is required to confirm this assumption. In the spirit of [12], one can increase the bit-rate using the same protocol by using an array of single-photon detectors, using for instance an EMCCD (electron-multiplying CCD) camera.
In the course of the project, we also considered the possibility of using a pair of APD and place them at the two output ports of a 50/50 beam-splitter. We would have then defined the value of each bit from the output channel of each detected photon. This solution is actually used commercially by Swiss company ID Quantique but the cost of the two APD prevented us from implementing it experimentally.
Acknowledgments
The work presented in this article was originally realized for the 2016 edition of the International Physicists’ Tournament. The authors thank the whole ENS IPT team and leaders for their help through the preparation of the tournament.
References
- R.L. Rivest, L.M. Adleman, A. Shamir, Cryptographic communications system and method, US Patent 4 405 829, 1983 [Google Scholar]
- Information technology – security techniques – encryption algorithms – part 3: block ciphers. Standard (International Organization for Standardization, Geneva, CH, 2010) [Google Scholar]
- A. Kerckhoffs, La cryptographie militaire, J. Sci. Mil. 9, 38 (1883) [Google Scholar]
- Z. Gutterman, L. Dorrendorf, B. Pinkas, Cryptanalysis of the random number generator of the windows operating system, ACM Trans. Inf. Syst. Secur. 13, 1 (2009) [Google Scholar]
- L. Torvalds, Linux kernel random.c (2005), https://git.kernel.org/cgit/linux/kernel/git/stable/linux-stable.git/tree/drivers/char/random.c [Google Scholar]
- P. L’Ecuyer, Uniform random number generators (Addison-Wesley, Reading, MA, 2010) [Google Scholar]
- P.C.M. Owens, J.G. Rarity, P.R. Tapster, Quantum random-number generation and key sharing, J. Mod. Opt. 41, 2435 (1994) [CrossRef] [Google Scholar]
- T. Symul, S.M. Assad, P.K. Lam, Real time demonstration of high bitrate quantum random number generation with coherent laser light, Appl. Phys. Lett. 98, 231103 (2011) [CrossRef] [Google Scholar]
- K.L. Vodopyanov, A. Marandi, N.C. Leindecker, R.L. Byer, All-optical quantum random bit generation from intrinsically binary phase of parametric oscillators, Opt. Express 20, 19322 (2012) [CrossRef] [Google Scholar]
- R. Lausten, G. Wu, I.A. Walmsley, P.J. Bustard, D. Moffatt, B.J. Sussman, Quantum random bit generation using stimulated raman scattering, Opt. Express 19, 25173 (2011) [CrossRef] [Google Scholar]
- D.J. Moffatt, J. Nunn, R. Lausten, D.G. England, P.J. Bustard, B.J. Sussman, Efficient raman generation in a waveguide: a route to ultrafast quantum random number generation, Appl. Phys. Lett. 104, 051117 (2014) [CrossRef] [Google Scholar]
- B. Sanguinetti, A. Martin, H. Zbinden, N. Gisin, Quantum random number generation on a mobile phone, Phys. Rev. X 4, 031056 (2014) [Google Scholar]
- G. Grynberg, A. Aspect, C. Fabre, Introduction to quantum optics: from the semi-classical approach to quantized light (Cambridge University Press, 2010) [CrossRef] [Google Scholar]
- P. Lewicki, T. Hill, Statistics: methods and applications: a comprehensive reference for science, industry, and data mining (StatSoft, 2006) [Google Scholar]
- G. Marsaglia, Keynote address: a current view of random number generators, in Proceedings, Computer Science and Statistics: 16th Symposium on the Interface (Elsevier, 1985) [Google Scholar]
Cite this article as: Hugo Roussille, Lionel Djadaojee, Frédéric Chevy, A simple quantum generator of random numbers, Emergent Scientist 1, 7 (2017)
All Figures
Fig. 1 Scheme of the durations received (each vertical bar represents a photon). tn is the arrival time of the nth photon and dn = tn+1 − tn. We define a random bit from the sign of dn − dm for sufficiently different values of n and m to avoid correlations between arrival times. |
|
In the text |
Fig. 2 Upper panel: Picture of the setup. The laser source is a 50 mW laser diode attenuated by two neutral density filters. Photons are detected using an avalanche photo-diode (APD) operated in single-photon counting mode. Lower panel: Example of detection signal. Two separated bins are separated by a 19 μs dead-time. |
|
In the text |
Fig. 3 Histogram of the duration between subsequent arrival times. Dots: experimental data; solid line: time between two emissions for the laser used in our setup. |
|
In the text |
Fig. 5 Results of the Monte-Carlo method for the calculation of π using the durations dn and dn+k, where k is the number of ignored events, for the determination of each bit. |
|
In the text |
Fig. 4 Autocorrelation function of the random sequence. |
|
In the text |
Current usage metrics show cumulative count of Article Views (full-text article views including HTML views, PDF and ePub downloads, according to the available data) and Abstracts Views on Vision4Press platform.
Data correspond to usage on the plateform after 2015. The current usage metrics is available 48-96 hours after online publication and is updated daily on week days.
Initial download of the metrics may take a while.