[ivlad]

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.

[red_admiral]

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.

[ivlad]

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.

[genewitch]

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?

[red_admiral]

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.

[ivlad]

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.

[less_less]

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

[tptacek]

This is deeply silly.

[ivlad]

… because?

Edit: yes, I read it and it is.