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.
OpenPGP_signature.asc
Description: OpenPGP digital signature
_______________________________________________ Gnupg-users mailing list Gnupg-users@gnupg.org https://lists.gnupg.org/mailman/listinfo/gnupg-users
