Extracting randomness from its root source

Random numbers are in high demand — from securing financial transactions, to running casino games, to seeding scientific simulations — but creating genuinely random numbers is a tough problem. Stephanie Wehner at the Centre for Quantum Technologies and her collaborators have analysed a new approach to creating randomness, proposing for the first time quantum analogues of widely-studied 'classical randomness extractors'.

The results have already led to a breakthrough in the 'noisy-storage model'. This model was introduced by Stephanie, an Assistant Professor in the National University of Singapore as well as a Principal Investigator at CQT, as a means to obtain security for tasks like secure identification in which two parties want to jointly solve a problem but don't trust each other. The new work links the security of this model to what is known as the quantum capacity.

The work was accepted for the prestigious CRYPTO 2012 conference and the paper appears in that conference's proceedings. The work was also presented in September at the QCRYPT conference held in Singapore.

Imagine that you have a classical system that looks like it is behaving randomly. An example is the Brownian motion of atoms — the path the atoms follow as they collide with one another is typically known as a 'random walk', but could be modelled given sufficient information about the atoms' initial positions and motion. The motion may be detected as thermal fluctuations. A randomness extractor is a function that combines a small amount of initial, real randomness (r) with the outcome of the measurement on such a system to generate a larger amount of real randomness (R). Crudely, the extractor is good if R is much bigger than the r that has to be invested.

But why rely on the randomness that comes from our imperfect knowledge of a classical system, when you could directly tap the randomness inherent in quantum theory? This is the question that Stephanie and her collaborators Mario Berta from ETH Zurich, Switzerland, and Omar Fawzi from McGill University, Canada, began with.

Quantum theory's randomness is one of its best known features. Einstein, bothered that quantum theory predicted some measurement outcomes to be unpredictable, famously said "God doesn't play dice". This was in the early 20th Century when the theory was still new. Quantum randomness has since been observed in experiments.

In their work, Stephanie, Mario and Omar consider some measurements that could be performed on a closed system of quantum bits (qubits) to extract randomness, even if the exact state of the quantum system is not known. They also derive fundamental bounds on the randomness obtainable, hich depends on how quantum entangled the observer is with the system. The bounds include the maximum amount of randomness that can be extracted for a given investment of initial randomness.

For practical applications, Stephanie notes that requiring the observer not to be entangled with the measurement apparatus is a safer principle to rely on for randomness than lack of knowledge, as must be assumed in the classical case. To become entangled, the observer would require both a quantum memory and a quantum interaction with the measured quantum system. Only if they managed to break into the laboratory to set up the entanglement before the measurements could they predict the random bits. It is a sharp contrast to the classical case, where information could be leaked or stolen from the lab at any time.

She is also excited that quantum to classical randomness extractors could support new theoretical insights. Classical randomness extractors are interesting not only for their practical applications, says Stephanie, "They are quite central in classical theoretical computer science. They are related to concepts such as complexity and error correcting codes".

The work is published as "Quantum to classical randomness extractors", Advances in Cryptology — CRYPTO 2012, Lecture Notes in Computer Science 7417, 776 (2012); arXiv:1111.2026.