deflating heffalumps (was: Betamax v. VHS, and the future of PQ-PGP)

[Jacob Bachmeyer]

On 1/2/25 18:25, Robert J. Hansen via Gnupg-users wrote:
> [...]
>
>>  The lowest common denominator will remain plain ECC or RSA, as it 
> > is today.  That’s bad.
>
> Why?  Breaking RSA-4096 via Shor's algorithm is straight out of 
> science fiction.  It requires 8k qubits for the computation alone: 
> once you take into account error correction, 40k or more qubits, all 
> in an ensemble with a decoherence time orders of magnitude beyond what 
> we have today. 

*THANK* *YOU*

I have been looking for hard numbers for the applicability of Shor's 
algorithm to RSA for a long time.  You have just provided the first hard 
numbers I have seen.  (I knew that at least 4096 qubits would be needed 
to hold a result, but apparently it needs far more than that.)

I have also long suspected that, while RSA key lengths beyond 4096 bits 
have diminishing returns against conventional computing, they may be 
more secure against quantum computing, perhaps even with increasing returns.

Also, can you cite a good source for how Shor's algorithm scales?  And 
how do analogous attacks on elliptic curve cryptosystems scale?  Thanks 
in advance.


-- Jacob