deflating heffalumps

[Jacob Bachmeyer]

On 1/2/25 22:59, Robert J. Hansen wrote:
>> 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.

Yes, but you seem to be missing my intended point:  each additional RSA 
key bit far less than doubles the work to factor the key on a 
conventional computer, but nonetheless always add 5 additional qubits to 
the requirements for Shor's algorithm.

"Only 5 more qubits" may not sound like much, but the difficulty of 
adding those compounds for each additional qubit.

In theory, with long-enough (perhaps too long for practical use) RSA 
keys, conventional factoring would be /easier/ than Shor's algorithm.  
Is there such a "turnover" point?

One of the rationales for limiting GnuPG RSA keys to 4096 bits is those 
diminishing returns against GNFS factoring, but raising that limit may 
be appropriate to enable greater quantum resistance. (Lack of 
interoperability for longer RSA keys might be another good reason to 
keep the 4096-bit limit.)

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

So those figures are low by factor of ...?  (Somehow I suspect that 
quantum error correction is considerably less efficient than 
Reed-Solomon...)

> [...]
>> 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".

So a quantum computer able to solve RSA-256/384/512 can also solve 
EC-RSA-256/384/512 with the same difficulty?

>> 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.
>
> [...]

And what about the various elliptic curve cryptosystems?


-- Jacob