[gruntled]

If anyone can build a big enough quantum computer (enough qubits) and prevent it decohering (that is, keeping it quantum long enough) to run Shor's algorithm, standard public key crypto like RSA would be broken. That has been known in theory since the 90s.

But if anyone ever builds such a quantum computer it isn't necessarily the end for public key crypto because there is a workaround that will work on classical computers, and that is to avoid trapdoor functions that can be broken by Shor's algorithm. So if a quantum computer comes along that can break, say, 256 bit RSA, we can save public key crypto by everyone switching to a different algorithm. That's the idea of post-quantum cryptography. And although RSA might be broken by a future quantum computer we can still have some sort of public key cryptography.

From the looks of this blog post, though, one of the new post-quantum public key algorithms can be broken. At least it could be if anyone ever makes a big enough quantum computer. And there's still the possibility that someone will find a trapdoor function that will be quantum resistant, so it isn't the end for all public key crypto.

tl;dr One more public key scheme might have fallen to a quantum algorithm. But the quantum hardware isn't there yet, so it's OK for now.

[SapphireSun]

I talked to a dude who made an interesting point about quantum computers. Quantum computations rely on particles behaving in a "quantum manner" in order for Shor's algorithm to reduce the big O complexity in factoring integers. However, at a certain size, you won't be able to entangle all the particles because there will be so many they'll start to behave like a macro material.

If true, this implies that quantum methods will only work up to a certain key size. Above that, you could run quantum computers in parallel, but now you're scaling your efficiency linearly instead of super-linearly, so hopefully having a huge (maybe impractically huge?) key size would be a sufficient defence. I understand that RSA gets substantially slower with larger keys though, so maybe it wouldn't be practical even if the key fits easily in memory.

I'm not an expert in physics or security, but I'd love for a physicist or cryptographer to comment as I thought that was a really intriguing argument.