"We were on the verge of giving up a few years ago because people were not interested in quantum at the time. Our name became a joke," said Andersen Cheng, CEO of the UK cybersecurity firm Post-Quantum. After all, he continued, how can you be post- something that hasn't happened yet?
But with billions of pounds, renminbi, euros and dollars (US, Canadian and Australian) being pumped into the development of quantum computers by both governments and the private sector and with that research starting to bear fruit, exemplified by Google's achievement of quantum supremacy, no-one's laughing now.
One day, perhaps quite soon, the tried and trusted public-key cryptography algorithms that protect internet traffic will be rendered obsolete. Overnight, a state in possession of a workable quantum computer could start cracking open its stockpiles of encrypted secrets harvested over the years from rival nations. Billions of private conversations and passwords would be laid bare and critical national infrastructure around the world would be open to attack.
A situation often compared with the Y2K problem, the impact could be disastrous. Like Y2K, no-one can be quite sure what the exact consequences will be; unlike Y2k the timing is unclear. But with possible scenarios ranging from massive database hacks to unstoppable cyberattacks on the military, transport systems, power generation and health services, clearly, this is a risk not to be taken lightly.
Critical infrastructure including power generation would be vulnerable to quantum computers
Post-quantum cryptography uses mathematical theory and computer science to devise algorithms that are as hard to crack as possible, even when faced with the massive parallel processing power of a quantum computer. However, such algorithms must also be easy to deploy and use or they will not gain traction.
In 2016, the US National Institute of Standards and Technology (NIST) launched its competition for Public-Key Post-Quantum Cryptographic Algorithms, with the aim of arriving at quantum-safe standards across six categories by 2024. The successful candidates will supplement or replace the three standards considered most vulnerable to quantum attack: FIPS 186-4 (digital signatures), plusNIST SP 800-56AandNIST SP 800-56B (public-key cryptography).
Not all types of cryptography are threatened by quantum computers. Symmetric algorithms (where the same key is used for encryption and decryption) such as AES, which are often deployed to protect data at rest, and hashing algorithms like SHA, used to prove the integrity of files, should be immune to the quantum menace, although they will eventually need larger keys to withstand increases in classical computing power. But the asymmetric cryptosystems like RSA and elliptic curve cryptography (ECC) which form the backbone of secure communications are certainly in danger.
Asymmetric cryptography and public-key infrastructure (PKI) address the problem of how parties can exchange encryption keys where there's a chance that an eavesdropper could intercept and use them. Two keys (a keypair) are generated at the same time: a public key for encrypting data and a private key for decrypting it. These keys are related by a mathematical function that's trivial to perform one in one direction (as when generating the keys) but very difficult in the other (trying to derive the private key from the corresponding public key). One example of such a 'one-way' function is factorising very large integers into primes. This is used in the ubiquitous RSA algorithms that form the basis of the secure internet protocols SSL and TLS. Another such function, deriving the relationship between points on a mathematical elliptic curve, forms the basis of ECC which is sometimes used in place of RSA where short keys and reduced load on the CPU are required, as in IoT and mobile devices.
It is no exaggeration to say that in the absence of SSL and TLS the modern web with its ecommerce and secure messaging could not exist. These protocols allow data to be transmitted securely between email correspondents and between customers and their banks with all the encryption and decryption happening smoothly and seamlessly in the background. Unfortunately, though, factorising large integers and breaking ECC will be a simple challenge for a quantum computer. Such a device running something like Shor's algorithm will allow an attacker to decrypt data locked with RSA-2048 in minutes or hours rather than the billions of years theoretically required by a classical computer to do the same. This explains NIST's urgency in seeking alternatives that are both quantum-proof and flexible enough to replace RSA and ECC.
NIST is not the only organisation trying to get to grips with the issue. The private sector has been involved too. Since 2016 Google has been investigating post-quantum cryptography in the Chrome browser using NewHope, one of the NIST candidates. Last year Cloudflare announced it was collaborating with Google in evaluating the performance of promising key-exchange algorithms in the real world on actual users' devices.
Of the original 69 algorithms submitted to NIST in 2016, 26 have made it through the vetting process as candidates for replacing the endangered protocols; this number includes NewHope in the Lattice-based' category.
One of the seven remaining candidates in the Code-based' category is Post-Quantum's Never-The-Same Key Encapsulation Mechanism (NTS-KEM) which is based on the McEliece cryptosystem. First published in 1978, McEliece never really took off at the time because of the large size of the public and private keys (100kB to several MB). However, it is a known quantity to cryptographers who have had plenty of time to attack it, and it's agreed to be NP-hard' (a mathematical term that in this context translates very roughly as extremely difficult to break in a human timescale - even with a quantum computer'). This is because it introduces randomisation into the ciphertext with error correction codes.
"We actually introduce random errors every time we encrypt the same message," Cheng (pictured) explained. "If I encrypt the letters ABC I might get a ciphertext of 123. And if I encrypt ABC again you'd expect to get 123, right? But we introduce random errors so this time we get 123, next time we get 789."
The error correction codes allow the recipient of the encrypted message to cut out the random noise added to the message when decrypting it, a facility not available to any eavesdropper intercepting the message.
With today's powerful computers McEliece's large key size is much less of an issue than in the past.Indeed, McEliece has some advantages of its own - encryption/decryption is quicker than RSA, for example - but it still faces implementation challenges compared with RSA, particularly for smaller devices. So for the past decade, Cheng's team has been working on making the technology easier to implement. "We have patented some know-how in order to make our platform work smoothly and quickly to shorten the keys to half the size," he said.
Post-Quantum has open-sourced its code (a NIST requirement so that the successful algorithms can be swiftly distributed) and packaged it into libraries to make it as drop-in' as possible and backwards-compatible with existing infrastructure.
Nevertheless, whichever algorithms are chosen, replacing the incumbents like-with-like won't be easy. "RSA is very elegant," Cheng admits. "You can do both encryption and signing. For McEliece and its derivatives because it's so powerful in doing encryption you cannot do signing."
An important concept in quantum resistance is crypto-agility' - the facility to change and upgrade defences as the threat landscape evolves. Historically, industry has been the very opposite of crypto-agile: upgrading US bank ATMs from insecure DES to 3DES took an entire decade to complete. Such leisurely timescales are not an option now that a quantum computer capable of cracking encryption could be just three to five years away.
Because of the wide range of environments, bolstering defences for the quantum age is not as simple as switching crypto libraries. In older infrastructure and applications encryption may be hard-coded, for example. Some banks and power stations still rely on yellowing ranks of servers that they dare not decommission but where the technicians who understand how the encryption works have long since retired. Clearly, more than one approach is needed.
It's worth pointing out that the threat to existing cryptosystems comes not only from quantum computers. The long-term protection afforded by encryption algorithms has often been wildly overestimated even against bog standard' classical supercomputers. RSA 768, introduced in the 1970s, was thought to be safe for 7,000 years, yet it was broken in 2010.
For crypto-agility algorithms need to be swappable
Faced with the arrival of quantum computers and a multiplicity of use cases and environments, cryptographers favour a strength-in-depth or hybridised approach. Cheng uses the analogy of a universal electrical travel plug which can be used in many different counties.
"You can have your RSA, the current protocol, with a PQ [post-quantum] wrapper and make the whole thing almost universal, like a plug with round pins, square pins or a mixture of both. Then when the day comes customers can just turn off RSA and switch over to the chosen PQ algorithm".
Code-based systems like NTS-KEM are not the only type being tested by NIST. The others fall into two main categories: multivariate cryptography, which involves solving complex polynomial equations, and lattice-based cryptography, which is a geometric approach to encrypting data. According to Cheng, the latter offers advantages of adaptability but at the expense of raw encryption power.
"Lattice is less powerful but you can do both encryption and signing,
but it has not been proven to be NP-hard," he said, adding: "In the PQ world everyone's concluded you need to mix-and-match your crypto protocols in order to cover everything."
Professor Alan Woodward (pictured) of Surrey University's Department of Computing said that it's still too early to guess which will ultimately prove successful.
"Lattice-based schemes seem to be winning favour, if you go by numbers still in the race, but there is a lot of work being done on the cryptanalysis and performance issues to whittle it down further," he said. "If I had to bet, I'd say some combination of lattice-based crypto and possibly supersingular isogeny-based schemes will emerge for both encryption and signature schemes."
Quantum mechanics can be an aid in the generation of secure classical encryption keys. Because of their deterministic nature, classical computers cannot generate truly random numbers; instead they produce pseudo-random numbers that are predictable, even if only to a tiny degree. One of Edward Snowden's revelations was that the NSA had cracked the random number generator used by RSA. More recently, weaknesses in RSA's random number generation were discovered in some IoT devices, where one in 172 were found to use the same factor to generate keys. However, a quantum random number generator (QRNG) produces numbers that are truly random, according to quantum theory, resolving this key area of vulnerability.
QKD commonly uses polarised photos to represent ones and zeros
Whereas post-quantum cryptography is based on maths, the other major area of research interest, quantum key distribution (QKD), is rooted in physics, specifically the behaviour of subatomic particles. QKD is concerned with key exchange, using quantum-mechanics to ensure that eavesdroppers cannot intercept the keys without being noticed.
In BB84, the first proposed QKD scheme and still the basis for many implementations, the quantum mechanical properties of subatomic particle, such as the polarity of a photon, is manipulated to represent either a zero or a one. A stream of such photons, polarised at random, is then sent by one party to a detector controlled by the other.
Before they reach the detector, each photon must pass through a filter. One type of filter will allow ones' to pass, the other zeros'; as with the polarisation process, the filters are selected at random, so we'd expect half of the photons to be blocked by the filtering process. Counterintuitively, however, their quantum mechanical properties mean that even those photons that are blocked' by a filter still have a 50 per cent chance of passing their correct value to the detector. Thus, we'd expect an overall agreement between transmission and detection of 75 per cent (50 per cent that pass straight through plus 25 per cent that are blocked' but still communicate their correct value).
Once enough photons have been transmitted to produce a key of the required length, the parties compare, over a separate channel, the sequence of emitted ones and zeros with the filter used for each, discarding the individual results where they disagree. A classical symmetric encryption key is then created from the remaining string of ones and zeros. This key can be used as an uncrackable one-time pad' which is then used to encrypt data such as a message or a login.
Should a man-in-the-middle intercept the stream of photons, the parties will be alerted because of the observer effect: measuring the state of a quantum particle will change it. Statistically, the number of photons registered as correct' by the detector will drop from 75 per cent to around 62.5 per cent and this will be noticed when the two parties compare a random sample of their results at the end of the process. Any such discrepancy will cause the key to be rejected. Properly implemented, QKD can be considered as a provably unbreakable method of exchanging keys.
Switzerland is a QKD pioneer, deploying the technology to secure electoral votes as far back as 2007. The company that helped to achieve this feat, Geneva University spin-off ID Quantique (IDQ), has since become one of the main manufacturers of QKD and QRNG hardware. CEO Grgoire Ribordy (pictured) has seen an recent upsurge of interest beginning in 2016 when the European Commission unveiled its 1 billion, ten-year Quantum Flagship programme. The market is now starting to mature, he said, adding that his company boasts customers in government, finance and "other organisations that have high-value IP to protect".
There's a certain rivalry between physics and maths, between QKD and post-quantum encryption, not least because funding has been hard to come by. Being hardware-based, QKD has so far gobbled up the lion's share of the research grants, but it's possible that when NIST returns its verdicts more money will flow into PQ. Arguments also rage over the practical limits of security.
"The physicists tend to talk about QKD as being perfectly secure' which sets the cryptographers on edge as there is no such thing in practice," Woodward said.
Ribordy is adamant that both techniques will be required. As with the hybrid approach to adopting algorithms, it's not an either-or situation; it all depends on the use case.
"I think they're actually complementary. Quantum crypto [another name for QKD] will provide a higher security and should be used maybe in backbone networks where there's a lot of at stake, big pipes must be protected with more security, and then the quantum-resistant algorithms can find an application in areas where security is not as critical or maybe where there's less data at stake."
One company that's looking to scale up QKD on a national basis is
the startup Quantum Xchange. Based in Bethesda, Maryland, USA, it was founded in 2018 with VC funding to provide ultra-secure data networks. President and CEO John Prisco (pictured) bemoaned the fact that his country, while forging ahead with quantum computers, is behind the curve when it comes to defending against them. It's possible that by 2024 when NIST selects its winning algorithms, the game will already be up.
"Everybody is saying, OK, let's fight quantum with quantum and I subscribe to that," he said. "We've got quantum computers that are offensive weapons and quantum keys that are the defensive of counterpart to that. The rest of the world outside of the United States is embracing this a lot more quickly - Europe, Japan and China."
Quantum particles are uniquely sensitive to any kind of disturbance, so while China may have successfully transmitted quantum keys between Earth and the Micius satellite, this was only possible because of ideal weather conditions at the time (although, interestingly, Woodward believes it could ultimately be the winning approach).
Particles transmitted through the more common fibreoptic cable are also limited by the tendency of the polarised photons to react with the medium. Even with the most pristine fibre, this limits real-world transmission distance to around 100km. After that, you need intermediary repeaters and trusted nodes' to relay the signal. Since it's not possible to directly clone quantum states, the quantum signal must be converted to classical and then back to quantum again, representing a weak point in the otherwise unbreakable chain. So trusted nodes must be very thoroughly secured, which inevitably increases costs and limits current applications. It is also possible for an attacker to interfere with emitters and detectors to corrupt the key generation process.
Other issues? Well, there's a lack of standards and certifications and the equipment is costly. Also, without some sort of secure signature process, how can parties exchanging keys be sure who they are exchanging them with? In addition, it's restricted to point-to-point communications and it's also incompatible with existing networks.
The theory is sound, said Woodward, but the engineering is still a challenge.
"It's in practice that QKD is encountering difficulties. For example, QKD is not yet at a stage where it is using single photons - it uses pulses of light. Hence, the very basis of not being able to clone the quantum state of a photon is put in question as there is more than one of them."
Woodward added that even after the kinks in QKD - be that via satellite, fibreoptic cables or over the airwaves - have been ironed out, the technology will still likely be confined to highly sensitive data and backbone networks because PQ cryptography will be easier to slot into existing infrastructure.
"Whichever [QKD] scheme proves most reliable and robust they all require that expensive infrastructure over what we have now, and so I can envisage it being used for, possibly, government communications but not for home users whose machines are picking a means to communicate securely with their bank's website," he said.
"The post-quantum schemes in the NIST competition would simply replace the software we already have in places such as TLS so the cost would be much lower, and the level of disruption needed for adoption by end-users would be far less."
However, Quantum Xchange is working on overcoming some of these limitations. The firm already operates a small number of high security QKD connections between financial institutions in New York and datacentres in nearby New Jersey over dedicated fibreoptic cables using trusted nodes to extend the reach of its QKD infrastructure. But it is also working on a hybrid system called Phio TX. This will allow the transmission of electronic quantum keys (i.e. keys created using a QRNG) or classical symmetric keys created from the quantum key via a secure channel separate from that used for the encrypted data. The idea is to make the technology more widely applicable by straddling the QKD-PQ divide and removing the point-to-point restrictions.
"The point is to be crypto-agile," Prisco said. "If a company is trying to come up with a quantum-safe strategy they can implement this product that has quantum-resistant algorithms, electronic quantum keys and optical quantum keys, so it becomes a level-of-service discussion. If you have a link that absolutely has to be protected by the laws of physics, you'd use an optical quantum key. If there's virtually no chance of someone intercepting the data with your key you could use a trusted exchange and the combination of the quantum-resistant algorithm with the quantum random number generated key is very powerful."
Edit: the original article stated the $1.2 billionNational Quantum Initiative Act was passed by the House of Representatives in December 2019 whereas this took place in December 2018.
Original post:
Inside the race to quantum-proof our vital infrastructure - http://www.computing.co.uk
