Technical Field

Examples of the present disclosure relate to methods of and apparatuses for generating a random number.

Background

Randomness is a resource of increasing importance, in areas such as scientific and engineering simulations, in statistical sampling, in probabilistic computation and in classical and quantum cryptography. Randomness is typically generated from hardware processes, which are considered nondeterministic, or by algorithms which are pseudorandom [1 ,2], A pseudorandom number generator uses a short input string, known as a “seed”, to produce a longer, seemingly random output string by applying a one-way function and an iterative algorithm. However, this process produces a deterministic sequence, as every specific seed will produce a specific outcome.

Another means of generating randomness is to use a random number generator (RNG), or entropy source. These are typically based on physical devices exhibiting a stochastic output, such as the thermal noise in electronic devices [3], or the amplitude in chaotic oscillators [4], In this manner, RNGs are considered nondeterministic.

The ultimate source of randomness is believed to be found in quantum devices. The collapse (by measurement) of an equal superposition between two quantum states will result in a fundamentally unpredictable outcome between the two possibilities. Quantum random number extractors are considered to be nondeterministic on a fundamental level, as opposed to physical devices exhibiting a stochastic output or entropy sources, which could, for example, be affected by temperature.

Some existing random number generators are based on this principle, whereby a single photon is prepared so as to create a superposition between the photon taking two different paths (for example, by the passing of the photon through a balanced beam splitter). Subsequently, the path is measured by a photon detector, and the outcome (that is, which path has been taken) determines the random bit value [5], In this method, for each passing photon, a random bit is generated. However, in practice, it has been noted that if the beam splitter deviates from its balanced setting even slightly, the random bit values are biased towards one of the two outcomes. As a result, in practice, these devices do not generate a uniform distribution of random numbers, and some debiasing has to be performed (that is, some post processing of the random bits is required in order to eliminate the bias). Such debiasing (for example, von Neumann debiasing [6]) involves discarding part of the data, and therefore, the debiasing affects the rate (that is, the entropy bits obtained per quantum event) of these devices.

It was suggested in [7] that if two adjacent time differences between detection events are respectively described by a Poisson process, then the resulting extracted random numbers can be said to be unbiased, mathematically. However, the rate at which such random numbers can be extracted is only 0.5 entropy bits per quantum event, on average. A good randomness extractor would be one that extracts random bits from an inherently uniform distribution of random values. However, as noted in previous work, the vast majority of processes which occur in nature have an associated non-uniform probability density function.

Summary

One aspect of this disclosure provides a method of generating a random number. The method comprises determining at least three or more random variables based on times of at least four independent events; and using the determined at least three or more random variables to generate a random number.

Another aspect of this disclosure provides an apparatus for generating a random number. The apparatus is configured to determine at least three or more random variables based on times of at least four independent events; and use the determined at least three or more random variables to generate a random number.

Brief Description of the Figures

For a better understanding of examples of the present disclosure, and to show more clearly how the examples may be carried into effect, reference will now be made, by way of example only, to the following Figures in which: Figure 1 is a graph illustrating the detection of five quantum events over a period of time;

Figure 2 is a flow chart of an example of a method 200 of generating a random number;

Figure 3 is a graph illustrating an efficiency E achieved as a function of a total number of ordered samples n

Figure 4 is an example of an apparatus 400 for generating a random number; and

Figure 5 is a schematic of an example of an apparatus 500 for generating a random number.

Detailed Description

The following sets forth specific details, such as particular embodiments or examples for purposes of explanation and not limitation. It will be appreciated by one skilled in the art that other examples may be employed apart from these specific details. In some instances, detailed descriptions of well-known methods, nodes, interfaces, circuits, and devices are omitted so as not obscure the description with unnecessary detail. Those skilled in the art will appreciate that the functions described may be implemented in one or more nodes using hardware circuitry (e.g., analog and/or discrete logic gates interconnected to perform a specialized function, ASICs, PLAs, etc.) and/or using software programs and data in conjunction with one or more digital microprocessors or general purpose computers. Nodes that communicate using the air interface also have suitable radio communications circuitry. Moreover, where appropriate the technology can additionally be considered to be embodied entirely within any form of computer- readable memory, such as solid-state memory, magnetic disk, or optical disk containing an appropriate set of computer instructions that would cause a processor to carry out the techniques described herein.

Hardware implementation may include or encompass, without limitation, digital signal processor (DSP) hardware, a reduced instruction set processor, hardware (e.g., digital or analogue) circuitry including but not limited to application specific integrated circuit(s) (ASIC) and/or field programmable gate array(s) (FPGA(s)), and (where appropriate) state machines capable of performing such functions. Embodiments of the present disclosure relate to methods for efficient, high-quality randomness extraction.

It has been noted, following the examination of time-ordered sequences of quantum events, that each possible ordering of the time differences between these events have an equal probability of occurring, regardless of the probability density function associated with these time differences. That is, it has been noted that the fact that each possible ordering of the time differences between these events have an equal probability of occurring, does not rely on the probability density function associated with these time differences being Poissonian. The probability density function may in fact be arbitrary, as long as the samples of the variable associated with this arbitrary probability density function (in this case, the time differences between the events), which then form the ordering, are independent.

It will be appreciated that, these orderings (which are uniformly distributed) may be then be utilized in a bias-free method for the extraction of random bits, or the generation of random numbers.

A proof of this uniformity is now described.

Firstly, consider a random variable X with a probability density function f(x). Consider that n samples are drawn from X, i.e. x ₁ ,x ₂ ,x ₃ ... x _n . It will be shown that each of the n! possible ways to order the drawn samples are both equally probable, and irrespective of (in other words, not dependent on) (x). Firstly, the case for n = 2 is considered. Suppose the first sample x _x has been drawn. Then, the probability of drawing x ₂ such that x _x < x ₂ is:

In these calculations, we have disregarded of the possibility of having x = x ₂ , but such a probability of this occurring can be approximated using Equation 15 below. If the probability for x _x < x ₂ is considered prior to drawing x _x , each of the outcomes for ₂ need to be multiplied with the probability for drawing x _x , such that

It is noted that this result does not depend on f(x).

The case of n = 3 is now considered. For n = 3 we can calculate P(x1 < x ₂ < x ₃ )

= 1/6 (9)

For a general n, P(x ₁ < x ₂ < x ₃ ... x _n ) similarly becomes Again, these probabilities are obtained irrespective of f(x) (that is, irrespective of the probability density function associated with the variables).

It is also noted that P x < ₂ < ₃ ...x _n ) is invariant under interchanging the indices of the samples, meaning that all possible orderings of n samples have the same probability 1/ n! of occurring. Therefore, the probability of obtaining one of the possible n! orderings is associated with a uniform distribution.

Figure 1 is a graph illustrating the detection of five quantum events over a period of time, where event 102 is detected at time t _{l t} event 104 is detected at time t ₂ , event 106 is detected at time t ₃ , event 108 is detected at time t ₄ , and event 110 is detected at time t ₅ . Figure 1 illustrates the results obtained from an experiment in which a quantum dot was initially excited with an 80MHz pulsed laser, and following this excitation, a photon was emitted from the quantum dot. The detection of this photon is the event 102 that is detected at time ti . Following this detection, the quantum dot was excited again after an appropriate cool down time had passed, and this process was repeated to detect photons emitted by the excited quantum dot at the times t ₂ , t ₃ , t and t ₅ . Thus, the time differences between the detected events in this experiment are the result of the cool down time, the time to excite the quantum dot, and the time at which an emitted photon is then detected. In this experiment, the cool down time ensures that the quantum dot does not retain memory relating to the previous excitation, such that each emission events is independent. Therefore, the time differences between the detected events in this experiment are closely related to the independent emission events, where each of these emission events is associated with a Poissonian distribution.

An example of how an ordering with the properties described above (which may then be utilized as part of the methods described herein) may be obtained from these events is now described. From the times of occurrences of these five events, four time differences can be determined and subsequently ordered. In this illustrated example, the ordering t ₃ - t ₂ < t ₄ - t ₃ < t ₅ - t ₄ < t ₂ - t _x is obtained. It will be appreciated that this ordering is one of 4! = 24 equally possible orderings of these time differences. That is, each of these possible 24 orderings of the time differences have an equal probability of being obtained.

As noted above, any of the possibilities x _t = Xj i,j G 1 ... n have been disregarded in the above calculations. However, such cases will have a nonzero probability of occurring in some examples. In such examples, the probability for such events depends on the precision d of the measurement and the distribution (x). For example, for two given samples x _x and x ₂ .

This probability is denoted p. The probability that at least two of the samples in sequence x _x , x ₂ ... x _n are deemed equal by the measurement is approximately:

Pfaii = P(at least 2 equal samples) = 1 — (1 — p) ) (15)

As illustrated above, the probability of drawing n samples from an arbitrary (but fixed) probability distribution in any of the n! particular orders is uniformly distributed. It will be appreciated that this uniformity may be exploited when generating random numbers and/or when designing random number generators. For example, this uniformity may be exploited by drawing a block comprising n samples (from an arbitrary, fixed, probability distribution). This block of n samples may then be mapped to a unique bit string. Following this, the block of n samples may be discarded, and a new block may be drawn to generate a further random bit string.

As noted above, when two or more of the n samples within the block are determined to be equal to one another, an ordering that is associated with a uniform distribution cannot be determined. In these cases, the samples comprised within the block may be discard, and a new block may then be formed comprising n further samples. In this example, the average, relative rate of discarded samples will be given by the probability described by Equation 15. The methods described herein for extracting randomness are described as bias-free, due to the fact that the possible orderings of the samples are uniformly distributed irrespective of the underlying distribution associated with the sampled variable. However, as noted above, there is a practical limit to how much randomness can be extracted per sample, due to the failure probability given by Equation 15.

Methods utilizing this uniformity can extract a much larger number of bits per detection event than prior art methods. An example method utilizing this uniformity is now described.

Figure 2 is a flow chart of an example of a method 200 of generating a random number. The method 200 comprises, in step 202, determining at least three or more random variables based on times of at least four independent events. Step 204 of the method 200 comprises using the determined at least three or more random variables to generate a random number. It is noted that, in alternative embodiments, step 202 may comprise determining at least two or more random variables based on times of at least three independent events.

As noted above, the method 200 enables the uniformity associated with the ordering of the determined at least three or more random variables to be utilized for bias-free random number generation. In this illustrated embodiment, each event has an associated detection time, and two adjacent events have an associated time difference. The number of possibilities to arrange a sequence of such time differences may then be utilized, as each of these number of possibilities has an equal probability of occurring, to both improve the efficiency of quantum random number generation, and provide fundamentally uniform randomness which does not require any post processing or debiasing.

The method 200 utilizes the times of at least four independent events. However, it will be appreciated that, in other embodiments, the method 200 may utilize an ordering of other independent samples of a variable that is associated with an arbitrary, fixed distribution, as such an obtained ordering will also then itself be associated with a uniform distribution. Therefore, these orderings will also be associated with the aforementioned advantages when utilized in methods of generating random numbers. In some embodiments, the at least three or more random variables are associated with an arbitrary, fixed, probability density function. For example, in embodiments in which the independent events comprise quantum emission events, the at least three or more random variables may comprise the time differences between adjacent pairs of the quantum emission events, where these time differences are then associated with a Poissonian distribution. Therefore, in some embodiments, each of the determined three or more random variables may comprise a time difference between pairs of events within the at least four independent events. In some embodiments, each of the determined three or more random variables comprise a time difference between adjacent pairs of events within the at least four independent events.

In some embodiments, the ordering of the determined at least three or more random variables is associated with a uniform distribution. That is, each of the possible orderings of the at least three or more random variables that could be obtained has an equal probability of occurring, regardless of the probability distribution describing the underlying variables. As noted above, this uniformity associated with the probability of obtaining a particular ordering may be utilized in methods for generating random numbers.

In some embodiments, the at least three or more random variables are different from one another. In the example described above, when two or more of the n samples within the block are deemed equal to one another, an ordering associated with a uniform distribution cannot be obtained.

In some embodiments, the step of determining at least three or more random variables based on times of at least four independent events comprises: determining whether any pair of the determined at least three or more random variables have the same value; and if so, determining a further at least three or more random variables based on times of at least four further independent events. It will be appreciated that alternative methods may be utilized following a determination that any pair of the determined at least three or more random variables have the same value to enable an ordering associated with a uniform distribution to be obtained.

In some embodiments, the independent events may comprise quantum events. For example, in some embodiments these may comprise photon emission events. For example, in some embodiments, the three or more random variables may correspond to the time differences between four quantum events, such as the detection of photons. As noted above, in embodiments in which the three or more random variables correspond to the time differences between the detection times of four photon emission events, the time differences will be strongly correlated with the emission times of the photon emission events.

In some embodiments, the three or more random variables may correspond to the time of occurrence or detection of four independent quantum events. For example, in one embodiment, four quantum dots may be excited simultaneously and the respective photons emitted by these quantum dots may then be detected. Each emission event will therefore be independent, and each respective detection time of the photons may then be utilized as one of the three or more random variables in accordance with the methods described herein.

It will be appreciated that by utilizing quantum events, the randomness extracted that is based on these events will be fundamentally random and unpredictable.

In some embodiments, the events may comprise independent classical events that are associated with an arbitrary distribution.

It will be appreciated that, in other embodiments, the at least three or more random variables may be passed on another property of at least four independent events. For example, in some embodiments, the at least four independent events may comprise independent classical events that are separated by an appropriate distance, and the at least three or more random variables may be determined based on these distances.

In some embodiments, the step of using the determined at least three or more random variables to generate a random number may comprise: mapping the determined at least three or more random variables to one of a plurality of values; and using the value to generate the random number.

In some embodiments, mapping the determined at least three or more random variables to one of a plurality of values to provide the random number may comprise mapping the order of increasing or decreasing magnitudes of the determined at least three or more random variables to one of the plurality of values. In some embodiments, the mapping may comprise a one-to-one mapping. One example of how an ordering of a sequence s of length n may be mapped onto a unique integer between 0 and n! - 1 is now described. Firstly, the sequence s is ordered in ascending order into a list s ₀ . Following this, for the element i = 1 in the sequence s, the position pos this element has in the list s ₀ is determined, and then the value (pos - l)(n - i)! is added to this result. The element is then removed from the list s ₀ , and this process continues for each entry in the sequence s for i = 2, 3, . . . n.

An example of the values that may be output for the possible orderings of a sequence length n = 3 are provided below:

The above table illustrates an example of each of the possible ways three unique samples may be ordered, and how an integer may then be assigned to each possibility. This implementation uses Mathematica’s Sort function which is based on lexicographic ordering, however in principle any 1 -to- 1 mapping of orderings onto unique integers may be used.

In some embodiments, the random number may be represented by a string of random bits. In some embodiments, the string of random bits may be generated by mapping the value to one of a plurality of strings of random bits.

It is noted that, in some embodiments, it may not be possible to map all of the obtained orderings of the sampled variables to bits, as n = 2 ^k (16)

Has only one nontrivial solution for n = 2 and k = 1. For other combinations of n and k, not all integers 0, 1, ... n! - 1 can be uniquely mapped to one element in 0, 1, ...2k - 1, while at the same time exhausting all of the latter elements. Therefore, to improve the efficiency of generation of random bits, values of n and k may be selected such that n! is slightly larger than 2 ^k (in other words, such that log ₂ (n!) has only a small fractional part, for example, log ₂ (65!) = 302.018, or log ₂ (986!) = 8390.009). For n = 986, a bias-free randomness extraction efficiency of about 8.5 entropy bits per sample is achieved, which is around 17 times the extraction efficiency obtained in [7],

E

Figure 3 is a graph illustrating an efficiency E (that is, the entropy bits per sample) achieved as a function of a total number of ordered samples n. In this example, measurement precision has not been taken into account, and so P _fail is assumed to be zero in Equation 17.

The values of n that correspond to the peaks illustrated in the graph, and their corresponding values of log ₂ (n!) are presented in the table below. It will be appreciated that selecting one of the following values of n will improve the efficiency of generation of random bits, as described above.

Figure 4 is an example of an apparatus 400 for generating a random number. In some embodiments, the apparatus 400 is operable to carry out the method 200 described above with reference to Figure 2. The apparatus 400 comprises a single-photon source 402. Photons emitted by the single-photon source 402 are detected by the detector 404. The time differences between adjacent detected photons may then extracted by the extractor 406, and the ordering of these time differences may then be utilized, in accordance with the aforementioned methods, in order to generate a random number (which, in this illustrated example, is represented by a plurality of entropy bits, or a bit string).

Figure 5 is a schematic of an example of an apparatus 500 for generating a random number. The apparatus 500 comprises processing circuitry 502 (e.g. one or more processors) and a memory 504 in communication with the processing circuitry 502. The memory 504 contains instructions executable by the processing circuitry 502. The apparatus 500 also comprises an interface 506 in communication with the processing circuitry 502. Although the interface 506, processing circuitry 502 and memory 504 are shown connected in series, these may alternatively be interconnected in any other way, for example via a bus. In one embodiment, the memory 504 contains instructions executable by the processing circuitry 502 such that the apparatus 500 is operable to determine at least three or more random variables based on times of at least four independent events, and use the determined at least three or more random variables to generate a random number. In some examples, the apparatus 500 is operable to carry out the method 200 described above with reference to Figure 2.

The general advantages of the proposed solutions in some examples are improved the efficiency of random number generation, and the provision of fundamentally uniform randomness which does not require any post processing or de-biasing.

Furthermore, it has been shown that such uniformity associated with these orderings does not rely on the underlying process being Poissonian, and that the underlying process may be associated with any arbitrary, fixed, PDF, as long as the events described by the process are independent. Therefore, the obtained ordering of a number of samples associated with other arbitrary, fixed, PDFs may also be suitable for use in methods for bias-free random number generation.

As no de-biasing has to be performed following the execution of such methods, the efficiency of these methods for random number generation are significantly improved.

It should be noted that the above-mentioned examples illustrate rather than limit the invention, and that those skilled in the art will be able to design many alternative examples without departing from the scope of the appended statements. The word “comprising” does not exclude the presence of elements or steps other than those listed in a claim, “a” or “an” does not exclude a plurality, and a single processor or other unit may fulfil the functions of several units recited in the statements below. Where the terms, “first”, “second” etc. are used they are to be understood merely as labels for the convenient identification of a particular feature. In particular, they are not to be interpreted as describing the first or the second feature of a plurality of such features (i.e., the first or second of such features to occur in time or space) unless explicitly stated otherwise. Steps in the methods disclosed herein may be carried out in any order unless expressly otherwise stated. Any reference signs in the statements shall not be construed so as to limit their scope.

References [1] A. C. Yao, “Theory and applications of trapdoor functions,” 23rd IEEE Symposium on Foundations of Computer Science, pp. 80-91 , 1982.

[2] M. Blum and S. Micali, “How to generate cryptographically strong sequences of pseudo-random bits,” SIAM J. on Computing, vol. 13, pp. 850-864, 1984.

[3] J. R. Millenson and G. D. Sullivan, “A hardware random number generator for use with computer control of probabilistic contingencies,” Behavior Research Methods and Instrumentation, vol. 1 , pp. 194 - 196, 1968.

[4] I. Reidler, Y. Aviad, M. Rosenbluh, and I. Kanter, “Ultrahigh-speed random number generation based on a chaotic semiconductor laser,” Physical Review Letters, vol. 103, p. 024102, 2009.

[5] T. Jennewein, U. Achleitner, G. Weihs, H. Weinfurter, and A. Zeilinger, “A fast and compact quantum random number generator,” Review of Scientific Instruments, vol. 71 , p. 1675, 2000.

[6] J. von Neumann, “Various techniques used in connection with random digits,” vol. 12, pp. 36-38, 1951.

[7] Y. He, W. Zhang, H. Zhou, L. You, C. Lv, L. Zhang, X. Liu, J. Wu, S. Chen, M. Ren, Z. Wang, and X. Xie, “Bias-free true random number generation using superconducting nanowire single-photon detectors,” Superconductor Science and Technology, vol. 29, no. 8, p. 085005, 2016.