October 13, 2014
New paper out on arXiv: https://arxiv.org/abs/1410.2790
We’ve built a machine that makes random numbers. Sounds easy? True randomness is quite tricky… Here is a bit of background and the idea of the paper:
Random numbers are important for quite a few applications, including cryptography (e.g. keeping your credit card details safe), computer simulations (of anything from your local weather report to astrophysics), and gambling.
In particular, in cryptography it is very important that your random numbers cannot be predicted by anyone else. If someone else can guess the numbers they can hack you. A few years ago, quite a few keys used on the internet were broken exactly because the randomness used to generate them was not good enough http://benlog.com/2012/02/16/its-the-randomness-stupid/ .
The easiest, and most common, way to generate random numbers is to take some input which is likely to be quite random, such as timing of keystroke inputs, the time of day, temperature etc. and then run it through a computer algorithm which spits out bits that look random. This works fine for some purposes, but although the output looks random it is really completely determined by the input, since anything the computer can do amounts to applying some fixed set of rules. If the inputs are not picked very carefully, the output may be less random than you think, and security can be compromised as it happened a couple of years back.
In fact, the problem is even more fundamental than that. Finding some truly random inputs to use is not easy at all. Think of flipping a coin for example. The outcome seems to be random, but if you would know the coin’s initial state (position, velocity, speed of rotation etc.) then the outcome could be predicted from Newtonian mechanics. This is true for all processes in classical physics – they are deterministic. So, we turn to the only place in nature where, as far as we know at the moment, we can get some true randomness: quantum physics.
In quantum physics, the outcome of measurements are not predictable even in principle. That is, even if you know the initial state of a system perfectly, it is not possible to predict with certainty the outcome of all measurements that can be made on it. That is very good from the perspective of creating randomness! If I generate my random numbers by measuring a quantum system, even if an attacker would know everything about how my system works and all the input parameters I use, there is no way he could guess my random bits. This is great, and in fact it is already used commercially for randomness generation. You can go and by a quantum random number generator, e.g. here: https://www.idquantique.com/random-number-generation/products/
In practice, to have some guarantee not just that your system is random, but on how random it is, you need to charaterise it quite well. Imagine that you are generating random numbers from a classical coin. Ideally, heads and tails are equally likely, but for any real coin there will be a slight bias towards one or the other. Similarly for a quantum random process, not all outcomes will be equally likely and this must be accounted for when extracting randomness. This can be done, but may be a little cumbersome, and in particular if the characteristics of the device changes over time, the guarantees that you had initially may no longer hold.
Here is where our new work comes in: we have a way to guarantee and quantify randomness in the output based on only a few general assumptions about the physical process. That is, in our approach you do not need to characterise the system very carefully. If there is a bias in the outcomes, the protocol will automatically correct for it, always ensuring that the output bits are completely random. Importantly, it does so in real time, so even if the bias drifts, it adapts. We can see this in our experiment by switching on an off the aircon in the lab. The change in temperature influences the quantum system, changing the bias, and we see a jump in the rate of randomness generation.
Published Paper: https://journals.aps.org/prl/abstract/10.1103/PhysRevLett.114.150501