deflating heffalumps

[Robert J. Hansen]

> Do I understand correctly that, while the complexity of
> conventional factoring scales with a logarithm of RSA key length,
> Shor's algorithm has a space requirement that scales linearly, but
> the engineering challenges implied by that linear growth scale
> exponentially?

The keyspace equivalency is made under the assumption the attacker is
using the generalized number field sieve. It's unsurprising for work
factors to be different for different algorithmic approaches. Your
conclusion is sound but please be careful not to draw inferences about
one approach from the behavior of the other.

> Are those figures including error correction or /before/ error
> correction?

Before.

> Agreed.  I also suspect that we may have practically-relevant PQC
> right under our noses, right now:  RSA.

Well, RSA is definitely quantum resistant. McEliece, another veteran 
algorithm, is widely believed to be truly post-quantum.

> Do the mathematical complexities that prevent conventional
> computing from making short work of 256-bit ECC keys also affect
> Shor's algorithm?

My understanding is "no".

> If not, that would mean that RSA is actually /stronger/ against
> future threats and TLS should be moving back to RSA and Diffie-
> Hellman posthaste.
The US government's belief is that RSA-3072 will be sufficient for 
protection of Top Secret/SCI data for the next twenty-five years.

(How do I know twenty-five years? Because whenever a document is 
classified, it gets an automatic declassification date. The default 
declassification date at the TS level is twenty-five years. So if NSA 
says TS/SCI data today may be protected with RSA-3072, it follows they 
don't believe quantum computing will break RSA-3072 for at least 
twenty-five years.)

https://media.defense.gov/2022/Sep/07/2003071834/-1/-1/0/CSA_CNSA_2.0_ALGORITHMS_.PDF