Quantum supremacy is almost uncertainly here

[harlan4096]

A quantum computer from Google solved a task that the best supercomputer in the world cannot. The news made quite a splash — and then, the report was retracted.

The retraction, which the Financial Times discovered on NASA’s website, only added more suspense to the situation. So, although exactly what task the quantum computer allegedly solved — not to mention how many qubits it deployed, 53 or 72 — remains uncertain, it’s actually very likely that the so-called quantum supremacy has indeed arrived. Bear with me and I’ll explain what makes me think so.

Quantum supremacy (allegedly) reached

Last year, impressed by the amount of attention post-quantum cryptography received at the RSA conference, we estimated that quantum supremacy could arrive toward the end of 2019. We took a simple estimate of the time required by quantum computers and supercomputers to factor the prime numbers for a 512-bit RSA encryption algorithm. These estimates are very close to reports — 3 minutes 20 seconds and approximately 10,000 years, respectively. So, does that mean our forecast was accurate?

It sounds like yes given the recent news. However, no one has (yet) had a thousand years to wait for a supercomputer calculation. But that’s not the most important thing here. It looks like time’s up for traditional cryptography. And that leads to the question: What should we do about it?

Cryptography might let us down. What can we do?

Whether you think of Edward Snowden as a hero or a traitor (or neither, or both), his divisive reputation reminds me of quantum systems — not necessarily one thing or another. In the context of the uncertain arrival of quantum supremacy, in Snowden’s new book he actually shares some good practical advice on encryption: use more than one algorithm. And he’s right. When you can’t be certain that your encryption will not fail, the best course of action is to encrypt your valuable data more than once, using different algorithms.

In the case of quantum computers, you just need to make sure that at least one of those algorithms is quantum-hardened. You can choose one of the 17 finalists NIST has chosen for the second round of selection, where lattice-based and multivariate algorithms seem to come out ahead of the disputed elliptic curves.

In the absence of a final selection, it might be a good idea from a business standpoint to continue using the readily available elliptic-curve cryptography on top of AES with sufficient key length, or SHA3, depending on what you need — because, as we already noted, valuable data requires “encryption maintenance” once in a while. Please never forget that.
...

Continue Reading