The race to save online privacy: what happens when quantum computers can break all our crypto?

Although many people are well aware of the many threats to their privacy, there is an underlying assumption that the use of strong encryption will always be available to mitigate those problems. Governments will doubtless continue to push for backdoors in encrypted Internet services like WhatsApp. But even if they do get their way by some misfortune, there are open source implementations that will remain beyond the reach of any government. As soon as commercial offerings are compromised, free software versions can step in for those who want such protection.

But suppose one day all crypto were broken? That’s always been a risk – we know that the NSA employs large numbers of top mathematicians, who presumably spend all their time trying to come up with ways to do precisely that. So far, though, there is no evidence that they have succeeded. Indeed, our most reliable source for this area, Edward Snowden, said specifically:

“Encryption works. Properly implemented strong crypto systems are one of the few things that you can rely on. Unfortunately, endpoint security is so terrifically weak that NSA can frequently find ways around it.”

That seems to be a pretty clear signal that the NSA had not been able to break the main encryption techniques, at least as far as Snowden knew in 2013, when he made this comment. However, whether or not the NSA or anyone else has made progress on that front since then, it is generally accepted that we are rapidly approaching a point when our current crypto techniques – even the strongest – can be broken through the use of quantum computers. A recent press release from the Eindhoven University of Technology called ‘The dark side’ of quantum computers explains:

“The expectation is that quantum computers will be built some time after 2025. Such computers make use of quantum-mechanical properties and can therefore solve some particular problems much faster than our current computers. This will be useful for calculating models for weather forecasts or developing new medicine. However, these operations also affect protection of data using RSA [Rivest–Shamir–Adleman] and ECC [Elliptic-curve cryptography]. With today’s technologies these systems will not be broken in a hundred years but a quantum computer will break these within days if not hours.”

Wikipedia’s English-language article offers a good introduction to the field of quantum computing for those who want to dive in more deeply. An article published a few months ago in the MIT Technology Review makes plain how quickly things are moving in this field. The qubits mentioned here are the basic units of quantum information used for computations – more is better:

“All the academic and corporate quantum researchers I spoke with agreed that somewhere between 30 and 100 qubits – particularly qubits stable enough to perform a wide range of computations for longer durations – is where quantum computers start to have commercial value. And as soon as two to five years from now, such systems are likely to be for sale. Eventually, expect 100,000-qubit systems, which will disrupt the materials, chemistry, and drug industries by making accurate molecular-scale models possible for the discovery of new materials and drugs.”

To put those numbers in context, it is generally held that a 50-qubit quantum computer would cross the “quantum supremacy” limit in computing, which is the point where even the most powerful traditional supercomputers can no longer compete. A few weeks ago, researchers announced that they had successfully tested a 51-qubit device. In other words, the quantum computing threat to general encryption is real, and getting closer by the day.

The Eindhoven news item accompanies a new (paywalled) paper published in Nature, also available as free preprint. Its title is “Post-quantum cryptography”, and it is unsurprisingly pretty tough going for non-specialists. But its key message is hopeful: that there are new encryption methods coming through that in theory are likely to be resistant to even high-end quantum computing machines. However, there is no guarantee it will be possible to build any practicable system that implements them. In particular, it’s an open question whether such advanced crypto will ever be available for widespread, routine use, as today’s methods are. That’s one clear problem. But there’s another, as the Eindhoven article warns:

“Without protection a lot of sensitive information will be out in the open, even data from years back. ‘An attacker can record our secure communication today and break it with a quantum computer years later. All of today’s secrets will be lost,’ warns Tanja Lange, professor of Cryptology at Eindhoven University of Technology. This concerns private data, bank and health records, but also state secrets’.”

Even if new encryption methods are introduced for future protection, there’s nothing to stop people using quantum computing to expose information that has been protected using today’s crypto. For example, the NSA or GCHQ might be storing encrypted emails and communications of interest that they have swept up as part of their global surveillance. Those might be impossible to read today, but in a few years’ time, when quantum computers are available to deep-pocketed intelligence agencies, the latter will be able to eavesdrop on all those conversations we thought were guaranteed to be private, which could have some interesting consequences in years to come.

Featured image by D-Wave Systems.