He is not wrong on the main claim, which is “All ECC (X25519-P521) will be broken by private sector quantum chips before RSA-2048 due to the physical limitations of stabilizing qubits.”
Shor’s algorithm is polynomial, however the number of qubits required is in order of O(log(n)^2), where n is the length of the key. Because ECC keys are much shorter (e.g., 256 to 521 bits) than RSA (2048 to 4096 bits), a smaller quantum computer would be needed to attack ECC.
RSA needs 4k (or 16k) keys because, with index calculus, these sizes reduce to a subproblem where you effectively need only 2^128 (or 2^256) time rather than the 2^{4k} for brute-force.
I think, but I may be misremembering, that you could apply Shor's algorithm to speed up index calculus by going for the subproblem directly? In this case RSA would fall too.
I note that the NSA recommendations are "move to post-quantum crypto", not "go back to RSA" so I infer that they think RSA-4096 might still be vulnerable.
I am not NSA, but I think their idea is something along the “once Shor’s algorithm is practical for key sizes of hundreds of bits, it’s only a matter of a few years of engineering effort to make it feasible for thousands bits long keys”. In other words, there is no sufficient safety margin for larger keys.
This is the first time in nearly 30 years I've ever heard the claim that you only need 18-20 qubits for something like a 256 bit key.
I've only ever seen the claims of 1:1 key bit to qubits. Aren't there existing claimed quantum computers with 20 qubits? Isn't Canada's machine an order of magnitude more qubits?
I think it matters not only how many qubits you have, but how they are "connected". As far as I know, it's a far easier problem to put N qubits in a chain with O(N) connections, than it is to have N qubits with O(N^2) connections to form a complete graph. And I believe the second example is what you need to do Shor's algorithm.
I am sorry, I should’ve read it twice before posting. I meant, QC to attack longer keys should be bigger proportionally. Number of operations is logarithmic. Silly me.
I'm not sure this is true anymore. There are recent improvements in quantum factoring algorithms, which significantly reduce the number of qubits required. See eg https://eprint.iacr.org/2024/222
