Encryption schemes used in modern cryptography make extensive use of random, unpredictable numbers to ensure that an adversary cannot decipher encrypted data or messages. Reliable random-number generators are therefore crucial. For instance, an Internet-wide analysis identified tens of thousands of servers that are vulnerable to basic attacks because of the use of poor-quality random-number generators1. In a paper in Nature, Bierhorst et al.2 exploit effects at the crossroads of quantum physics and special relativity to demonstrate the ultimate random-number generator, achieving unprecedented security.
Read the paper: Experimentally generated randomness certified by the impossibility of superluminal signals
Although schemes to generate random-looking numbers are easy to come up with, assessing their security — the extent to which they are truly unpredictable to a potential adversary — is notoriously difficult. Much of the trouble stems from the fact that such schemes cannot be tested by merely looking at their output from a black-box perspective: that is, a perspective from which the internal workings are unknown. For instance, certain arithmetic operations known as pseudorandom number generators produce sequences of numbers that are completely predictable. However, these sequences do not have any recognizable patterns and thus, from the perspective of someone who does not know how the numbers have been generated, they cannot easily be distinguished from sequences obtained by truly random methods.
It would therefore seem that security can be established only if the random-number generator satisfies two conditions. First, the user must know how the numbers have been generated to verify that a valid procedure is being implemented. And second, the system must be a black box from the adversary’s perspective to prevent them from exploiting knowledge about its internal mechanism.
However, the first condition is unrealistic. A random-number generator can deviate from its intended design because of imperfections, component ageing, accidental failures or explicit tampering by an adversary, leading to undetected biases. And monitoring the internal mechanism of a random-number generator in real time is both impractical and difficult3. Moreover, the second condition violates Kerckhoffs’s principle — a central tenet of modern cryptography that was reformulated by the father of information theory, Claude Shannon4, as “the enemy knows the system being used”. In other words, cryptographic systems should be designed under the assumption that an adversary will quickly gain familiarity with them.
Remarkably, thanks to the unusual laws of quantum physics, it is possible to create a provably secure random-number generator for which the user has no knowledge about the internal generation mechanism, whereas the adversary has a fully detailed description of it.
To understand how this works, consider the experiment carried out by Bierhorst and colleagues (Fig. 1). The authors prepared two photons in a peculiar quantum condition known as an entangled state. They then sent each photon to a different remote measurement station, where the photons’ polarizations were recorded. During measurement, the photons were unable to interact with each other — the stations were so distant that this would require signals travelling faster than the speed of light. Nevertheless, the measurement outcomes were strongly correlated because of the photons’ entangled nature. Such correlations can be detected experimentally through statistical criteria known as violations of Bell inequalities5.
The strong correlated behaviour of the two remote photons suggests that they could be used to devise a faster-than-light communication device. This would indeed be possible unless the photons’ measurement outcomes were unpredictable, in which case any attempt to use such photons in a communication device would fail, because it would result in scrambled, indecipherable messages. Because faster-than-light communication is impossible, it follows that violations of Bell inequalities imply random measurement outcomes. That is, the violations provide an experimental signature of randomness.
This conclusion depends only on the impossibility of faster-than-light signalling and not on any detailed description of the associated quantum systems. It must therefore be true from an adversary’s perspective, regardless of their particular knowledge of the quantum processes being carried out. And because violations of Bell inequalities can be verified by a user only from the statistics of the observed outputs of such processes, the verification procedure represents a black-box test of randomness.
Violations of Bell inequalities have been observed in numerous experiments over the past three decades5, and their qualitative connection to randomness has been known for many years. However, quantum-information researchers have started to develop the tools to exploit this connection only in the past few years6.
A key difficulty has been that most experiments that violate Bell inequalities are affected by loopholes, meaning that they cannot be considered as black-box demonstrations. For instance, the constraint that the two photons cannot exchange signals at subluminal speeds was not strictly enforced in the two previous demonstrations of randomness generation based on Bell inequalities7,8. In the past few years, loophole-free experiments have been carried out9–11, but they remain a technological challenge. In particular, the magnitude of the Bell-inequality violations observed in these experiments, although sufficient to confirm the correlated behaviour of the photons, was too low to verify the presence of randomness of sufficient quality for cryptographic purposes.
Bierhorst and co-workers have improved existing loophole-free experimental set-ups to the point at which the realization of such randomness becomes possible. However, this threshold is barely reached. Every time a photon is measured in the authors’ experiment, the randomness that is generated (expressed as bits; 0s and 1s) is equivalent to tossing a coin that has 99.98% probability of landing on heads.
Over many runs, the sequence of measurement outcomes should have accumulated enough uncertainty that truly random bits could be extracted through clever post-processing. However, no existing methods for analysing such sequences would have been efficient enough to reach this goal. Bierhorst et al. therefore introduced a powerful statistical technique, tailored to the weak Bell-inequality violations they observed, that achieved this aim. Ultimately, the authors were able to generate 1,024 random bits in about 10 minutes of data acquisition — corresponding to the measurement of 55 million photon pairs.
Bierhorst and co-workers’ random-number generator represents the most meticulous and secure method for producing randomness that has ever been demonstrated. However, its generation rate is much lower than in more-conventional commercial quantum random-number generators, which can produce millions of random bits per second12. Nevertheless, improvements in the generation rate can reasonably be expected to the point at which this will no longer be a strong limiting factor.
More problematic is the size of the authors’ random-number generator: it is comprised of measurement stations that are 187 metres apart to prevent subluminal signalling between the photon pairs. This distance might be reduced in the future, but it is hard to imagine how it could reach the dimensions of more-standard electronic hardware (at most, a few centimetres) using foreseeable technology.
Although Bierhorst and colleagues’ study will therefore not directly lead to practical, consumer-grade random-number generators, it sets a new direction and ideal for the secure production of random bits. The authors’ approach and theoretical methods could be adapted to much more practical and simple designs for random-number generators that potentially retain many of the conceptual and security benefits of their work.
via Nature https://go.nature.com/2k0annt
April 11, 2018 at 10:15AM