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
_______________________________________________
Gnupg-users mailing list
Gnupg-users@gnupg.org
https://lists.gnupg.org/mailman/listinfo/gnupg-users
