Post-quantum defaults

[Jacob Bachmeyer]

On 4/6/26 15:40, Robert J. Hansen via Gnupg-users wrote:
>> Can you elaborate on why  you think  this is the right time to do so?
>
> My three pillars are the difficulty of accumulating a large enough 
> ensemble; the difficulty of quantum error correction; and the general 
> inefficiency of quantum computers. These are all to some degree 
> interconnected.
>
> For instance, there's a theoretical minimum of 5n+1 qubits necessary 
> to break RSA-n, but at our current level of engineering it requires 
> orders of magnitude more. That's an inefficiency problem that runs 
> into "so, how do you plan to get that many qubits anyway?" (large 
> ensemble problem) and "how do you plan on doing error correction on 
> that huge ensemble?" (error correction).
>
> Well, there's been some news there.
>
> [...]
>
> Maybe.[2] Cain, Xu, King, et al., just a few days later showed that 
> maybe it can be done in 10,000 physical qubits.
>
> Serious cracks, indeed. [...]

The issue I see here is that these seem to be specialized for elliptic 
curve cryptosystems.  In other words, the "free lunch" of shorter keys 
and better performance by using the more-complicated mathematics of 
elliptic curves instead of the general integers is going away.

This is almost *exactly* what I expected and is the concern that I have 
long had with EC cryptosystems:  the shorter ECC keys will fall to 
quantum computing long before the longer RSA keys will.

The theoretical minimum you cite means that 10241 qubits are required to 
break RSA-2048 and 20481 qubits are required to break RSA-4096, for 
example; while resistance to conventional factoring scales 
logarithmically with key length, simply doubling the RSA key length 
doubles the number of qubits needed to attack the key---and this 
relationship is linear /ad infinitum/, while the difficulty of building 
larger ensembles increases exponentially in qubit count.

Further, as you mention, those are the ultimate logical qubits required 
to run Shor's algorithm; actual implementations will require many 
physical qubits to support each of those logical qubits.

Assuming that Shor's algorithm "sees through" the mathematical 
complexity of elliptic curves (i.e. the cost of using Shor's algorithm 
is the same for ECDLP-256 and RSA-256), those 10000 physical qubits 
represent about 39n to break RSA-n.  This is 79872 qubits to break RSA-2048.

Lastly, Bruce Walzer's reply notes that both of these appear to be 
hypothetical and the "10000 qubits to crack ECDLP-256" uses a technology 
that has yet to actually work, while Google's paper apparently assumes a 
significant noise reduction that is also yet to be proven.


-- Jacob