The race for quantum-resistant cryptography
Image credit: Dreamstime
That large-scale universal quantum computers could break widely used encryption methods is well known, but what was once seen as a distant, even theoretical, problem is now driving the latest technology race.
There isn’t yet a universal quantum computer big enough to break the widely used public key encryption systems, such as RSA, that secure everyday online information exchanges. Nor does anyone know when there will be. But with many predicting a significant breakthrough this decade, companies and governments are racing to launch cryptographic solutions so they can claim a stake in what is expected to be a billion-dollar market.
Public key encryption is based on the assumption that factoring integers – whole numbers – with several hundred or more digits is practically impossible. An algorithm known as Shors showed that a quantum computer could meet the challenge, however, allowing bad actors to decrypt information and spy on communications without detection. And they wouldn’t even need a phishing email to do it. What’s more, governments are increasingly concerned about the risk of ‘harvest and decrypt later attacks’, whereby an adversary steals sensitive information to decode when they have the quantum capability.
Yet developing cryptographic defences for a threat that has not yet materialised and uses information belonging to a notoriously mind-blowing realm of physics is no mean feat. Most advanced quantum cryptography efforts, such as random number generation (RNG) and quantum key distribution (QKD), still have technological limitations. But there’s no doubt the field is experiencing its most exciting decade yet, with commercial quantum cryptography solutions now emerging.
UK-based Arqit is an interesting example. The firm, started by David Williams, a former investment banker and founder of telecom satellite company Avanti, has garnered much debate within quantum crypto circles for its somewhat opaque solution that uses neither QKD nor RNG.
The firm says it has invented a new, patented quantum protocol called Arc19 powered by satellites, which are set to launch in 2023. Its technology is a downloadable-to-any-device platform-as-a-service called ‘QuantumCloud’ that will initially be used for quantum-resistant communication between defence aircraft and drones and control centres, as well as blockchain, but could also work for Internet of Things (IoT) and smart city applications. Arqit has already signed a flurry of deals with major firms such as Babcock, BT, Verizon, and Northrop Grumman, as well as “large government customers globally”, which it says it can’t talk about.
According to its founder, the satellites send information encoded into the quantum properties of photons, which the laws of physics determine can never be stolen, to data centres on Earth.
When one device wants to create a key with another, they both use their architect software to talk to different data centres to access an identical set of random numbers. Using these, they can create a brand new shared random number and ephemeral key to communicate securely. Keys can be created infinitely and work inside a pre-existing algorithm called AES256 (The Advanced Encryption Standard), which the US National Security Agency already recommends as ‘safe’ against attacks by a large quantum computer because it uses a sufficiently large key.
The simplicity of the technology can “seamlessly make the world secure”, according to Williams. “Although our tech stack contains transformational deep technological innovation, and our software protocol endpoints are completely new, we’re injecting keys into an algorithm that you already have installed on all of your devices – no revolution required,” he adds.
Arqit describe the system as “trustless” because the keys are never created by a third party; not even the satellites know what they are. This solves a fundamental problem with QKD satellite protocols: that data can be sent either globally or trustlessly, but not both, says Williams.
“Anyone who is trying to build a system that does QKD by satellite is wasting their time; it doesn’t work. If you can’t send keys globally, you’re of no interest to the internet. If you can’t send keys trustlessly, you’re not secure,” explains Williams. “No one has ever devised a cryptographic system which can make endless computationally secure, trustless and ephemeral keys. That is a world first.”
Rhys Lewis, head of the Quantum Metrology Institute at the National Physical Laboratory, doesn’t agree with the first point, however: “QKD over satellite removes the need for trusted nodes as the signal can be picked up from one point and transmitted directly to the receiving station. Only the satellite must be trusted,” he explains.
QKD by satellite is a key area of research and development, as it’s thought it can help overcome some of the range problems experienced by QKD via optical fibre. The UK and Singapore have a £10m initiative to co-develop QKD Qubesat, a satellite based on the CubeSat standard that will use a pioneering QKD technology to test the secure distribution of cryptographic keys over globe-spanning distances.
QKD protocols provide a mechanism for two remote parties to agree a shared secret key, where the key cannot be observed or tampered with by an adversary without alerting the original parties.
Last year, industry leader Toshiba launched the fruits of 20 years of research into development of QKD over optical fibre. Its commercial hardware and management software combines RNG and PQC (Post-Quantum Cryptography) technologies for an all-in-one package that Toshiba will use to build the world’s first commercially available quantum-secured metro network with BT. The network will connect the London financial and creative industries with data centres to the west of the city. It’s expected to be operational in early 2022. Previously the two companies connected two industrial facilities in Bristol using 6km of fibre-optic cable that shared encryption keys using a stream of single photons.
Rather than only point-to-point, the new project will operate as a mesh, connecting various nodes to create end-to-end secure communications, according to Toshiba. But it faces several restrictions. Quantum cryptography protects the transport of the keys between the nodes; however, the nodes need to be placed in secure locations, which is usually the central office of the telecom operator.
“No cryptographic technology is trustless – you can’t make cryptography technology without trusting someone,” says Andrew Shields, head of the quantum technology division at Toshiba Europe. However, he adds, using multiple paths for keys in the network can protect against attack on any single node.
‘No cryptographic technology is trustless – you can’t make cryptography technology without trusting someone.’
Another challenge is that the range of a single link within the network is 150-175km, which Toshiba hopes to extend. In June its Twin Field QKD system transported keys between nodes of 600km with the apparatus housed in a single lab.
Lewis says these are “not intractable” problems but simply need “engineering and technological development”, which is under way.
In June, scientists at the University of Science and Technology of China created a secure quantum fibre link over 511km between two Chinese cities by using a relay in the middle that didn’t have to be trusted.
Toshiba says its technology will eventually be used with satellites, for which it is working with Arqit, among others, for quantum fibre networks within national and continental areas, such as across Europe. The European Union has a similar ongoing project. The satellites will act as another trusted node creating a secure link between the various fibre networks in different regions.
This is no mean feat, points out Andersen Cheng, CEO of Post-Quantum, a company developing PQC technology. “JPMorgan has more than 5,000 branches; linking all of them using quantum fibre-optic cable may not be possible. It might just be key data centres are connected instead,” he says.
Toshiba is targeting scale though. It recently announced it had developed the world’s first chip-based QKD system that could in the future reduce the size and weight of the technology and enable mass manufacturing, making it applicable for IoT and other solutions.
“This will allow us to maybe even bring it into the home – we can think about a set-up like a set-top box. It will allow a much wider deployment of the technology in the future, it’s difficult to tell when, but maybe in five to ten years’ time,” says Shields.
Ultimately just how worried should the world be about universal quantum computers being used to steal sensitive data or potentially starting cyber warfare? That depends on who you ask. Predictions range from the next few years to over ten. Williams says the incentive for a ‘doomsday computer’ that can steal everyone’s information is practically unlimited, and therefore equal resources will be thrown at it.
Piers Clinton-Tarestad, a partner and global technology risk quantum computing leader at EY, says he advises clients to start thinking about the threat now, taking a risk-based approach. “If people wait for new standards to come out and then start looking at it, they’re going to be behind the curve, but they shouldn’t jump on the bandwagon either.”
Professor Peter Kruger at Sussex University perhaps has the most reassuring answer: “I wouldn’t be worried because the development of quantum cryptography is much faster than that of quantum computers,” he says. “It’s a race between the two and cryptography is currently winning.”
Quantum vs post-quantum
In 2016, the US’s National Institute of Standards and Technology (NIST) launched a world-leading open-source competition to find post-quantum encryption (PQC) algorithms – these are based on mathematics as opposed to quantum technologies – that can be implemented on current computing technology and software.
From 69 submissions, only 15 remain, with first standards expected to be ready by 2024.
NIST says the goal of PQC (also called quantum-resistant cryptography) is to develop cryptographic systems that are secure against both quantum and classical computers, and can interoperate with existing communications protocols and networks.
PQC will be a vital line of defence against a universal quantum computer attack according to Dustin Moody, a mathematician in the NIST Computer Security Division, because it doesn’t require specialist hardware and equipment that isn’t accessible to most people.
Like the crypto systems used today, post-quantum ones are built using extremely complicated mathematical techniques. The security of RSA, for example, hinges on the fact it’s hard to factor a number into its prime parts when the numbers are hundreds and hundreds of digits long.
Most of the remaining competition candidates are based on a mathematical system known as ‘lattices’. These are composed of a collection of geometric points and structures – that look like the top of a pie – with a periodic repeating pattern.
“The basic idea is to create a set of keys, a public and a private or secret key. The public key is known to everybody, which is necessary to send information. To contact that key, a certain computation is done, specified by the algorithm, and in which there is a trap door built, so that if you know the private key you can accept what is being sent,” explains Moody.
UK-based company Post-Quantum is a finalist with the only non-lattice scheme, known as Classic McEliece. Its algorithm is based on error-correcting code methodology that deliberately introduces random errors into the process so that every time there is an encrypted output it looks different. This is known as being ‘semantically secure’ because looking at the outcome it’s impossible to tell where the input came from.
Andersen Cheng, CEO of Post-Quantum, is critical of the UK government’s effort to develop its own publicly available PQC algorithms and instead focus on commercialising quantum technologies.
“Ours is a very British achievement, but in a typical British way in that we had absolutely no support from anyone,” he says. “The UK is spending billions trying to build a Frankenstein monster [quantum computer] but when that monster comes out, we don’t have a cage to contain it because it’s not part of the budget.”
To garner confidence in the security of a particular algorithm in the competition, it’s tested against all known and published attacks, which it must stand up against. The hope is, if the parameters are high enough, it would take too long for even a quantum computer to break it.
However, some are critical of the NIST PQC algorithms, noting they haven’t been studied for as long as today’s public key cryptography and quantum cryptography is more secure.
Moody disagrees. “These two types of cryptosystems – post-quantum and quantum – will provide slightly different functionalities that work together to give us all the security that we need,” he explains. “Cryptography that gets most widely adopted around the world is typically that which is publicly available and so has had good security analysis, giving people confidence in it.”
Overall, says Moody, he has more confidence in free and open-source cryptography that has gone through global public vetting, rather than systems developed privately by companies, but adds that NIST can’t provide ‘guarantees’ either. “We can’t prove that no one will ever come up with some brilliant algorithm that would crack it. But we know that all known algorithms won’t break it, and the more people that have been trying to study and break it the more confidence you can have.”
Sign up to the E&T News e-mail to get great stories like this delivered to your inbox every day.