Author: Cambridge Quantum Computing – cambridgequantum.com
Protecting your data against a quantum adversary requires more than implementing post-quantum algorithms. Despite the security industry’s intense focus on the NIST competition and the widespread awareness of Shor’s algorithm, a quantum-powered adversary will be able to do more than factor large numbers.
Quantum computers are adept at finding patterns in data and modelling complex physical systems. This is why they are poised to revolutionize machine learning and drug discovery. Unfortunately, it also means they will be excellent tools for cybersecurity hackers. Random numbers are at the heart of all cryptographic systems, and today most of those random numbers are generated using non-quantum-proof techniques.
In this article, we’ll explain how CQC has adopted a revolutionary approach to generating provably-perfect entropy, which we use to create quantum-proof cryptographic keys (both classical and post-quantum). We share the results of running this entropy generation on an IonQ quantum computer, with help from TKET and the Amazon Braket service. Finally, we’ll close with a tutorial to help you run your own experiments.
Why Quantum Computers Threaten Random Number Generation
The goal of a random number generator is to produce completely unbiased and private streams of random bits. Each bit should have a 50% chance of being a zero or a one, with an attacker having no ability to predict this. This is what makes them usable in cryptography.
Today, there are three broad approaches to randomness generation. The first is to use pseudo-random number generators (PRNGs), which use software algorithms to expand an initial “seed” value into a random-looking sequence of bits. Because PRNGs are deterministic, the output is completely predictable to anyone who can figure out the seed.
The second approach measures erratic physical systems to produce random outputs. In this category are so-called true random number generators (TRNGs) and many existing quantum random number generators (QRNGs). In a TRNG, the physical system being measured is a predominantly classical process, such as thermal noise in a diode. QRNGs observe the results of quantum processes, such as the route a photon takes when it hits an angled silvered mirror.
The approaches described above all suffer from the same problem: they are completely dependent on correct physical construction and perfect modelling of the random number generator. In short, the device has to be completely trusted.
As we mentioned above, a quantum computer is well suited for modelling complex physical systems. As a result, a quantum adversary could potentially model these devices and predict their output. Even a non-quantum adversary could begin to predict the output if the device degrades over time: a common issue in complex physical systems involving lasers and precise angles. So in terms of post-quantum security, these RNG approaches are fundamentally flawed.
Fortunately, there is a third approach, which we will discuss in this article. Cambridge Quantum Computing has developed the first provable QRNG, known as IronBridge, which uses quantum computers to generate unbiased private entropy. Unlike the other two approaches, this is invulnerable to a quantum adversary, and it produces self-tested randomness.
IronBridge generates cryptographic keys using this entropy, resulting in quantum-proof keys (for both classical and post-quantum algorithms). Such keys are invulnerable to the most powerful quantum attacker.
How IronBridge Generates Keys Using Quantum Computers
IronBridge relies on the intrinsic randomness of quantum-mechanical systems. Unlike standard QRNG approaches, we treat the quantum computer as a black box and pass it circuits to execute. The output of the circuits is used to generate our entropy, as well as acting as a self-test to ensure the quantum computer is functioning correctly. This means we no longer have to place complete trust in the device.
More specifically, IronBridge takes imperfect (biased or not fully private) randomness and amplifies it using a quantum computer, resulting in perfectly unbiased and private data with unconditional security. This verified randomness and privacy amplification is only possible with quantum devices, thanks to the physical phenomenon of entanglement, which allow us to exhibit quantum effects from a device without having to characterize it. By comparing the inputs and outputs we can quantify the entanglement in the device and obtain an explicit value for the error in the device.
We measure the quantum effect by running a Bell test, which can be viewed as a test for “quantum correlations”. Certain correlations between inputs and outputs are exclusively quantum and can only be achieved if the device uses entanglement, assuming there are no loopholes in the test setup.
In our protocol, we use a three-qubit Bell test to evaluate the Mermin correlator M. This results in a value between zero and four, where anything above two indicates quantum correlations (i.e. entanglement). Furthermore, the value of M tells us how much entanglement was exhibited, thus quantifying the performance of the device. This value dictates how much randomness and privacy the outcomes have (see here for further technical details), allowing us to extract only the intrinsic quantum randomness. If M is not greater than 2, we abort the protocol.
Recently, we’ve made improvements to the protocol, allowing for increased randomness generation rates. We continue to work with our partners and academic collaborators to optimize and improve our protocol, both in terms of hardware-specific implementation and theoretical analysis.
You can read more about our entropy generation protocol in our paper; this is the heart of our IronBridge platform and creates the raw entropy we use to generate our quantum-proof cryptographic keys. But now we’ll move on to running these circuits using Amazon Braket.
Running IronBridge Circuits on Amazon Braket
To test the protocol on Amazon Braket, we ran four different three-qubit IronBridge circuits on an IonQ device. The circuits were composed of H, CX, S and Sdg gates. These are all supported by the Braket SDK. Therefore the only thing we needed to do before passing the circuit to the BraketBackend was a noise-aware placement of the qubits:
from pytket.routing import NoiseAwarePlacementNoiseAwarePlacement(backend.device()).place(circuit)
The above line assigns the circuit’s logical qubits to physical nodes on the device, taking into account the device architecture and noise characteristics (which are obtained from Braket when the backend object is constructed).
This device allows a maximum of 10,000 shots per job. Our experiment was split over several jobs running successively, and the results accumulated until we had a million shots per circuit. This took about 24 hours of elapsed time.
Once the experiment was complete, we calculated the Mermin correlator M. In this case,
M = |<001> + <010> + <100> – <111>|
Where <> denotes the correlator function for one of the circuits, i.e. the probability of even parity in outputs minus probability of odd parity in outputs. The bit strings encode different circuits. For example,
<001> = [P(000|001) + P(011|001)+ P(101|001) + P(110|001)] – [P(001|001) + P(010|001) + P(100|001) + P(111|001)]
where P(m|c) is the probability of measuring m given the circuit encoded by c.
The result of our IonQ experiment was M = 3.702. This is above the classical maximum of 2, proving that the device exhibits quantum correlations (it must have used entanglement). In fact, this value for the Mermin correlator is higher than any publicly reported in literature as far as we are aware, on either quantum computers or single-purpose devices. It is close to the theoretical maximum of 4, showing that small qubit devices are starting to reach maturity with very low error rates.
Contact Us to Learn More and Trial the Technology
If you would like to trial our QRNG technology, get in touch with us. We are happy to share examples of our entropy for statistical testing or to discuss proof-of-concept and production deployments.
We continue to optimize the protocol and physical implementations to improve generation rates and further reduce the minimal underlying security assumptions. We work with our collaborators to run on different hardware, including devices from IBM, AQT and Honeywell.
This concludes our overview of generating perfect randomness on quantum computers. If you want to try out TKET and Amazon Braket for yourself, a quick how-to can be found here.
Get in Touch to Learn More
If you’d like to learn more about any of the topics in this article, such as TKET or our IronBridge QRNG, please contact us.
