Leveraging Latest Quantum Algorithms to Optimise Train Scheduling
Cambridge Quantum and Honeywell
Cambridge Quantum Announces Largest Ever Natural Language Processing Implementation on a Quantum Computer
Cambridge Quantum Releases TKET Version 0.7
Cambridge Quantum Develops Algorithm to Accelerate Monte Carlo Integration on Quantum Computers
Cambridge Quantum and Total Announce Multi-Year Collaboration
Cambridge Quantum Announces Integration of TKET Platform into Strangeworks Ecosystem
Leveraging Latest Quantum Algorithms to Optimise Train Scheduling
A new method to efficiently perform factoring would defeat modern encryption systems.
And Shor had just provided the theoretical method for doing it.
The Threat from Quantum Computing
Despite such advances, there are varying opinions on when Shor’s Algorithm may pose a serious threat to cybersecurity, with estimates ranging from five to 20 years. One factor suggesting a shorter timescale is the faster-than-Moore’s Law trajectory of current quantum hardware. Honeywell, for instance, believes it can increase the power of quantum computers by a factor of 10 every year for the next five years, yielding an increase in power of 100,000x by 2025.
Does this mean you should wait until “Q Day” to become concerned? Absolutely not: The need to protect infrastructure systems is more immediate than that, for three reasons.
First, it takes time to upgrade security software, and massive infrastructure that corporations or governments utilise can require months or even years to make this transition.
Second, there are rumors that adversarial governments and other bad-faith actors are archiving data now in anticipation of future decryption capabilities, known as a “harvest-now, decrypt-later” attack. This means, for example, that the encrypted files of a future jet fighter could be stolen now and later decrypted.
Third, Shor’s Algorithm is a proof that efficient decryption of RSA is realisable but is by no means the most efficient way to accomplish this; there have already been substantial improvements upon the original algorithm.
It is entirely possible that tomorrow a clever researcher could develop a vastly more efficient method of decryption, placing us that much closer to cybersecurity vulnerability. Thus, enterprises should consider making the transition as soon as possible.
Fortunately, intense effort is already underway to develop new cryptographic algorithms resistant to quantum hacking.
In 2016 the National Institute of Standards and Technology invited submissions for such “Post-Quantum Encryption (PQE).” Intense study followed as mathematicians, computer scientists and physicists did their utmost to defeat such submissions using quantum technology, both existing and theoretical. From the original 82 submissions, there are currently seven finalists. The winners are expected to be announced between 2022 and 2024. There will likely be a few algorithms selected, with a tradeoff between security and power consumption.
Protection Using Quantum Technologies
While it has become well-understood that quantum technologies can be used to attack communications, what is lesser known is how they can be used to protect communications. In particular, their role in an often overlooked yet fundamental aspect of cybersecurity: randomness.
Randomness is most often associated with cryptographic keys or passwords. An obvious property of such keys is that their method of generation should be non-deterministic. Any mathematical formula or pattern in such supposedly random generation would render its usefulness null.
The other essential aspect is its security. After its generation, there should not be any means for an adversary to gain knowledge of what this key is. Both these number generation and security issues are directly relevant to quantum computing.
Let us first consider number generation. While we all have an intuitive sense of what randomness means, have you ever considered how to generate a truly non-deterministic random number? Your first instinct may be to toss a die. But consider that the die obeys the laws of physics, which are completely understood and completely predictable. If you measured the speed and direction of your toss, the air pressure, the weight of the die and so forth, and then performed careful calculations to compute the trajectory, you would predict the outcome with 100% certainty. The fact that such modeling is possible means that this outcome is not at all random.
If we generalise this concept, we realise that any method using classical (non-quantum) physics is deterministic. This includes asking a classical computer to generate random numbers. While they can certainly generate pseudo random numbers, the computer merely follows a formula based on internal, obscure data (such as the number of milliseconds to have elapsed since the last restart) to calculate numbers that only superficially appear random. All of this could be modeled by a quantum-powered attacker.
The answer to producing true randomness lies in quantum physics. Quantum physics is based on superposition, the idea that a system can exist in multiple configurations simultaneously. Measuring the system then forces it to choose one of these configurations.
To produce the quantum equivalent of a coin toss, prepare a quantum state in a 50% “1” state and 50% “0” state, and then measure it. This will result in a “1” or a “0” outcome with equal probability. Performing this operation several times results in a string of 1s and 0s corresponding to a random key.
There are a number of commercially available quantum random number generators (QRNGs) that attempt to measure quantum processes like this. While such QRNGs may be entirely viable ways of producing random keys, there is a shortcoming related to their security. If an adversary were to tamper with the quantum states, or at least eavesdrop, how would one know? The output is simply 1s and 0s, and so it would be impossible to determine if this were secure or not.
This is not merely a hypothetical: “Quantum Hacker” Vadim Makarov demonstrated that he was able to influence the output of quantum tunneling by shining a flashlight on the photodetectors. A similar issue would occur if the performance of the QRNG degraded over time – something that is quite feasible in a complex device that relies on mirrors and lasers.
Are we then cursed to have this theoretically random-but-insecure means of producing cryptographic keys? Fortunately, quantum mechanics comes to the rescue once again.
Quantum physics is based on superposition, the idea that a system can exist in multiple configurations simultaneously. Measuring the system then forces it to choose one of these configurations.
Playing Dice with the Universe
Albert Einstein famously commented, “God does not play dice with the universe.” Apparently, He (or She) does, and in 1964 Irish physicist John Bell proved it.
Bell developed a mathematical method to distinguish quantum processes from classical ones. This was based on quantum entanglement, the idea that the quantum state of one particle can be correlated with another, even if physically separated. Entanglement is a purely quantum property with no classical counterpart.
By focusing on entanglement, Bell provided a precise means of identifying quantum (and therefore random) processes from classical (and therefore deterministic) processes. And since any tampering or eavesdropping would require classical means, Bell also provided a proof of the outcome’s security. There is no longer any trust in devices required, only fundamental physics.
New approaches to cryptographic key generation are being developed that build on this trustless entanglement technique. These approaches offer guarantees (and proof) that the keys are perfectly random in nature and haven’t been influenced by any attacker, quantum or otherwise. As we move toward a quantum future, technology like this will be critical to maintaining the security we enjoy today.