deflating heffalumps

[Jacob Bachmeyer]

On 1/2/25 20:47, Robert J. Hansen wrote:
> [...]
>
>> 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.
>
> Following the (very rough) rule of thumb that each additional bit 
> requires two additional qubits, then yes, RSA can in some sense be 
> viewed as post-quantum already, since you can ratchet its difficulty 
> up arbitrarily to whatever level of quantum resistance you want. 
> Afraid of an adversary with science fiction hardware and a 20kbit 
> ensemble? Use RSA-16384 and sleep easy.

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?

Examples from Wikipedia ("Key size") include a 3072-bit RSA key having a 
2**128 work factor, but reaching 2**256 against /conventional/ computing 
requires a 15360-bit RSA key.  On the other hand, those same RSA keys 
would require 15k and 75k qubits, respectively?  Are those figures 
including error correction or /before/ error correction?

> I am wholly in favor of research into PQC and encourage the adoption 
> of PQC where appropriate. However, I am also wholly in favor of 
> thinking deeply on the words "where appropriate".

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

>> Also, can you cite a good source for how Shor's algorithm scales?
>
> https://arxiv.org/pdf/quant-ph/9602016 is the standard paper. I seem 
> to recall we've improved on it slightly since, but not by much.

Thank you.  I will enjoy reading that later.

>>  And how do analogous attacks on elliptic curve cryptosystems scale?
>
> My understanding (which is limited: I'm not Scott Aaronson) is that 
> Shor's algorithm, expressed in its most generic form, applies to any 
> hidden-subgroup problem. That means discrete logs will fall to it in a 
> similar way. I can't guarantee the 5N+1 rule will hold true, but I 
> would definitely expect a kN+c rule with small values for k and c.

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

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.


-- Jacob