deflating heffalumps

[Robert J. Hansen]

> I have been looking for hard numbers for the applicability of Shor's 
> algorithm to RSA for a long time.

They're hard to come by, because we mostly only know theoretical limits. 
  It requires a flat minimum, last I checked, of quantum gates on the 
order of (lg N)^2(lg lg N)(lg lg lg N) to run the algorithm, more to 
store a result, and so on.

Turns out I misremembered the equation for breaking RSA via Shor: it's 
not RSA-N requires 2N+1 qubits, it's 5N+1 qubits for any realistic N. I 
regret my error. (Cite will appear later in this email.)

As the size of the ensemble increases, so too does the risk of error. At 
factoring 15 you have little risk of error; at a 4096-bit number it's 
enormous and the number of qubits you're wasting on error correction 
goes through the roof. And since the larger the ensemble the larger it 
takes to make the ensemble, so too do your coherency times have to grow: 
if your ensemble decoheres before you're done assembling it, you're out 
of luck.

The engineering challenges involved are far and away the greatest 
humanity has ever imagined.

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

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

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

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

> Thanks in advance.

Sure! Hope this helps.
-------------- next part --------------
A non-text attachment was scrubbed...
Name: OpenPGP_signature.asc
Type: application/pgp-signature
Size: 236 bytes
Desc: OpenPGP digital signature
URL: <https://lists.gnupg.org/pipermail/gnupg-users/attachments/20250102/f134d0f6/attachment.sig>