Post-quantum defaults

[Jacob Bachmeyer]

On 4/6/26 22:47, Robert J. Hansen wrote:
>> The issue I see here is that these seem to be specialized for 
>> elliptic curve cryptosystems.  In other words, the "free lunch" of 
>> shorter keys and better performance by using the more-complicated 
>> mathematics of elliptic curves instead of the general integers is 
>> going away.
>
> Yes. But attacks only get better over time: they don't get worse.

Yes.  But there are hard physical requirements (like needing enough 
qubits to store the key) that will always be higher for any practical 
RSA than for EC cryptosystems.  (RSA-256 falls easily to conventional 
factoring, while 256-bit ECC keys are common.)

> If the current defaults of ECC keypairs are at threat, and our 
> original projection for RSA-2048 was it would be safe only until 2030 
> or so (see the GnuPG FAQ, section 11.2), then the solution is not to 
> go back to RSA-2048 but to find something with long-term prospects. 
> That would seem to be Kyber, not RSA-4096.

That calculation seems to be based on the projected advance of 
conventional computing.  Quantum computing is different and will break 
ECC keypairs long before it can touch even RSA-1024 or RSA-768 (which 
are already now considered broken by conventional means).

That FAQ also claims that 256-bit ECC is equivalent to RSA-16384.  
Perhaps we should actually add RSA-16384 (which requires at minimum 
81921 qubits to crack) and take the advances in conventional computing 
as the enabling factor for such (ludicrously) large keys.

(On a side note, how many bits are needed for a Kyber keypair?)

>> This is almost *exactly* what I expected and is the concern that I 
>> have long had with EC cryptosystems: the shorter ECC keys will fall 
>> to quantum computing long before the longer RSA keys will.
>
> Perhaps.

There is no "perhaps" here:  Shor's algorithm apparently solves ECDLP 
with the same difficulty as it solves RSA.  The hard part is getting 
enough qubits to perform the operation for a given key size to actually 
work at once.

That is an engineering problem that will progress from smaller ensembles 
to larger ensembles, possibly hitting a wall along the way, possibly 
not.  Either way, it is certain that quantum computing ensembles 
sufficient for cracking 256-bit keys will exist before larger ensembles 
that can crack 2048-bit keys will.

More entertainingly, we will likely find out that someone has such an 
ensemble when Bitcoins start "disappearing" from wallets...


-- Jacob