Quantum computing concerns?

post by len.hoang.lnh (len-hoang-lnh) · 2019-05-06T23:04:26.395Z · score: 14 (11 votes) · EA · GW · 4 comments

Contents

  Projections for Quantum Computing
  Consequences of 4,000-qubit Computing
  Conclusion
4 comments

Hi all,

I have recently been wondering if quantum computing should be regarded as a major concern for mankind's safety. Perhaps not as an existential risk. But perhaps as a major catastrophic risk.

In particular, there might be a non-negligible risk that, within a few years, quantum computing might lead to an escalation that might turn into civil or global war. Since I have never read any major concern regarding this risk, I am quite skeptical of my own concerns. Thus I'd be very curious to have feedback from you.

Projections for Quantum Computing

It all started a few weeks ago, as I prepared a science popularization video (in French) on quantum computing, and in particular on Shor's algorithm. In brief, this is a quantum algorithm that efficiently breaks current asymmetric cryptography protocols, which are widely used throughout Internet, industries and governments. In particular, it seems that the security of banking systems heavily relies on asymmetric cryptography. They would be breakable by Shor's quantum algorithm.

As often in popularization of this topic, I first wrote a reassuring conclusion that basically said that quantum computers were not yet powerful enough to run Shor's quantum algorithm. And thus that viewers could sleep in peace.

But I wanted to be quantitative, so I looked up the number of qubits of latest quantum computers. I got shocked. While I was expecting this number to be of ~50 qubits, it turns out that "in December 2018, IonQ reported that its machine could be built as large as 160 qubits". While I actually am skeptical of this claim, it nevertheless seems worrying.

This number of (entangled) qubits is critical to the capabilities of quantum computers. In particular, a n-bit cryptographic asymmetric key could roughly be broken by a n-qubit quantum computer. Today's (RSA) keys often are kilobytes long. This means that they might be broken by, say, a quantum computer with 4,000 qubits.

(Note that even symmetric cryptography often relies on Diffie-Hellman secret sharing protocol, which is vulnerable to quantum attacks. In particular, all systems currently protected by such a cryptography can be broken by quantum algorithms. It thus seems that any private content you share can potentially be made public by 4,000-qubit computers.)

So, according to Wikipedia, it seems that the number of qubits might have tripled within the last year. At this rate, it would take three years for quantum computing to be powerful enough to upset most of our current cryptographic systems.

Evidently, I may be overestimating this rate. At Moore's law rate (doubling every 18 months), it would take 7.5 years. And it's not unlikely that quantum entanglement of thousands of qubits will never be doable.

But it seems that there is also a lot of secrecy in this industry. Thus we may not be aware of what is really going on in industry's labs. Also, it seems that we should not discard the possibility of a major breakthrough. Thus, though I may be completely wrong, it seems to me that we should regard 4,000-qubit quantum computing as a plausible scenario within the next few years.

Consequences of 4,000-qubit Computing

While there are proposals for secure cryptography in a quantum world, like quantum cryptography or post-quantum cryptography, such quantum-resilient systems have not been deployed so far. They might not have been deployed by the time a 4,000-qubit quantum computer will have been built. Thus, it seems that we cannot exclude the possibility that quantum computers will become efficient in a world where classical asymmetric cryptography is still very widely used.

Yet it seems to me that if this occurs, then there is a huge risk of major economical disturbance, accompanied with fears and possible supply shortages, which might then lead to a civil or global wars. In fact, a mere fear of quantum hacking may suffice to trigger such disasters.

Indeed, as I said, banking systems (among many other industries) heavily rely on asymmetric cryptography. Thus, any suspicion of possible quantum hack might motivate banks to freeze all accounts. This may cause payment failures, which would break trusts between different parties. Supply chains might be interrupted. And there might be no foreseeable solutions in short to medium term, while huge information systems are being updated and verified to be secure.

If this situation lasts for a day, we probably would be fine. But given how hard it is to safely update information systems, the chaos caused by the interruption of information systems might last for days, weeks, and perhaps months. And given how reliant we are on information systems, this might cause disruptions in electricity or food supply, which might lead to panic and conflicts.

Conclusion

Our modern world strongly relies on information systems, whose security too often relies on asymmetric cryptography. This cryptography is well-known to be vulnerable to quantum algorithms like Shor's. So far, no quantum computer is powerful enough to implement Shor's algorithm to break actual asymmetric cryptographic keys. However, given the current rate of progress, perhaps we should consider the possibility that they will be powerful enough within a few years.

What do you think? Are these concerns justified? If not, what am I missing? And if they are, what can be done to anticipate the advent of quantum computing?

4 comments

Comments sorted by top scores.

comment by RavenclawPrefect · 2019-05-07T03:55:21.411Z · score: 9 (6 votes) · EA · GW

It seems to me that there are quite low odds of 4000-qubit computers being deployed without proper preparations? There are very strong incentives for cryptography-using organizations of almost any stripe to transition to post-quantum encryption algorithms as soon as they expect such algorithms to become necessary in the near future, for instance as soon as they catch wind of 200- and 500- and 1000- bit quantum computers. Given that post-quantum algorithms already exist, it does not take much time from worrying about better quantum computers to protecting against them.

In particular, it seems like the only plausible route by which many current or recent communications are decrypted using large quantum computers is one in which a large amount of quantum computation is suddenly directed towards these goals without prior warning. This seems to require both (1) an incredible series of both theoretical and engineering accomplishments produced entirely in secret, perhaps on the scale of the Manhattan project and (2) that this work be done by an organization which is either malicious in its own right or distributes the machines publicly to other such actors.

(1) is not inconceivable (the Manhattan project did happen*), but (2) seems less likely; in particular, the most malicious organizations I can think of with the resources to pull off (1) are something like the NSA, and I think there is a pretty hard upper bound on how bad their actions can be (in particular, "global financial collapse from bank fraud" doesn't seem like a possibility). Also, the NSA has already broken various cryptographic schemes in secret and the results seem to have been far from catastrophic.

I don't see a route by which generic actors could acquire RSA-breaking quantum tech and where the users of RSA wouldn't also be able to recognize this event coming months if not years in advance.

*Though note that there were no corporations working to develop nuclear bombs, while there are various tech giants looking at ways of developing quantum computers, so the competition is greater.

comment by PabloAMC · 2019-05-09T22:17:23.722Z · score: 7 (2 votes) · EA · GW

From the perspective of a PhD student in quantum computing, I would say that one should not worry excessively about quantum computing breaking cryptography. This is mainly for two reasons:

1. As pointed on other comments by RavenclawPrefect and beth, so called "post-quantum" cryptographic algorithms are being developed that should not be vulnerable to cryptography (NIST holds a contest to develop the future standard). I am not specially skilled on particularly this topic, but it seems that some approaches regarding Hash functions or lattices could be feasible. This are just the usual kind of public key mathematical cryptography, but with harder problems.

2. Even in the highly unlikely situation where the above point fails, quantum stuff gives you a solution: quantum cryptography is theoretically invulnerable to almost any kind of attacks. I say theoretically, because quantum devices are not perfect and an adversary may be able to exploit this to take advantage. The most famous quantum key distribution algorithms are called BB84 (the first one to be discovered) or Arthur Ekert's one based on Bell Inequalities. To the best of my knowledge, the research edge now is on the topic of "Device independent quantum cryptography", in which you are supposed to be using a device from a supplier that you may not trust. This path to secure cryptography is more physical one: just find a way to perform private key distribution in a safe way.

In conclusion, I do not expect cryptography to suffer from QC making it unfeasible, but rather it seems more likely that cryptography will become even harder to break.

That said, I am actually trying to figure out in my PhD if there could be any interesting areas of research where QC may be useful in the field of AI Safety. Arguments for it are that there exists a research topic called Quantum ML which is in its infancy still. On the other hand, AI safety may not require any specially compute expensive algorithms, but rather the right approaches (also maybe with higher level of abstraction you would have in QC). I say this because I would be very interested in hearing from anyone who would like to work on similar topics (because they have this background in particular) and/or would have particular hindsights for ideas that could help.

Thanks!

comment by beth​ · 2019-05-07T18:20:53.457Z · score: 4 (3 votes) · EA · GW

1. The mechanics of cryptographic attack and defense are more complicated that you might imagine. This is because (a) there is a huge difference between the attack capabilities of nations versus those of other maligne actors. Even if the NSA, with its highly-skilled staff and big budget, is able to crack your everyday TLS traffic, doesn't mean that your bank transactions aren't safe against petty internet criminals. And (b) state secrets typically need to be safe against computers of 20+ years in the future, as you don't want enemy states to capture your traffic now and decrypt it as soon as slightly better hardware is available.

2. NIST is running a project at this moment to standardize a post-quantum cryptographical protocol. Cryptographers from many countries in the world are collaborating on this. The tentative timeline lists the completion of the draft standards in 2022-2024.

Hence, experts worldwide estimate that strong quantum computers will not be deployed even by intelligence agencies until well into the 2030s (e: 40's). Consumer targets will stay safe for even longer than that.

comment by Milan_Griffes · 2019-05-07T07:33:34.596Z · score: 3 (2 votes) · EA · GW

Have you checked with Scott Aaronson about this? He's very credible about things quantum, and I believe is fairly bearish about the current state-of-the-art.