[Cryptography] The race to Quantum machines.

Jon Callas jon at callas.org
Tue May 28 20:33:03 EDT 2019

As others have said, there's a lot to slip between the cup and the lip.

We should prepare for the eventual creation of quantum computers, of course, and this means continued investment in post-quantum cryptography, especially because as we deploy it, we're going to find interesting implementation glitches that have serious security issues. We'll get through them of course, but there's going to be a decade in which "hybrid" encryption where we use both conventional and post-quantum asymmetric algorithms will be *less* secure than conventional encryption because the weakest point is going to be the issues in the post-quantum.

Also as others have said, building bigger quantum computers is likely to get harder the more qubits one makes. The theory people say that the theory is all done and all that's left is "just engineering problems." Let us also remember that colonies on the moon, cities on Mars, and useful fusion power are also just engineering problems. Yet, let's cast those aside for the moment.

If we start with some basics, like IBM releasing 20 qubits this year, and assume a Moore's-Law like doubling of bits, we need ~20 generations of doubling to get to the needed ~20M qubits. If that doubling is every year-and-a-half, then we get there around 2050. If it's every two years, around 2060.

(For what it's worth, I have a standing bet that they can't break 4K RSA by 2050. I picked this because it's about where RSA runs out assuming Moore's Law continues in classical computers indefinitely.)

So there's where some reasoning can come from. Yes, a more efficient algorithm that decreases the number of qubits by 100x is good, but that's only 6.5 generations of doubling. The clock speed of the generation is more important -- if there's another 100x efficiency, but the doubling takes six months longer, then it's pretty much a wash. We're still talking about it really being practical in the 2050-2060 time period.

Far more important is that exponent. We assumed that it's 2 (doubling) per generation. If it's not 2 but the square root of 2 (~1.4), then we hit that point in the early 2080s, not the 2050s (assuming a 1.5 year generation). This is a completely reasonable thing for it to be; silicon has the nice feature that halfing the element size gets you 4x the transistors, not 2x. 

I made myself a spread sheet to calculate some of these numbers. I made variables for generation clock tick, generation increase, and just played around.

Now consider that their paper lets you break a key in eight hours. With a static TLS key for a site, that's powerful, but with ephemeral keys, there's still a pretty big haystack for those needles.

The bottom line, I think is that while yes plan for quantum computers, but it's not the cakewalk some claim it will be.


More information about the cryptography mailing list