Why can't we just increase the bit length to counteract shor's algorithm?

Question

I know that it sounds like a very stupid question but if Shor's algorithm has a complexity of roughly $n^3$ why cant we just increase the bit size until the time for the algorithm to run is unfeasible on a quantum computer or would it just take too much memory and too much computation for RSA/ECC to be worth it?

Answer 1

if shor's algorithm has a complexity of roughly n^3 why cant we just increase the bit size until the time for the algorithm to run is unfeasible on a quantum computer

The problem is that the amount of work needed by the honest parties is also roughly $n^3$, hence we don't have that much advantage over an attacker.

To be fair, we do have a few advantages:

• For RSA, there are optimizations available for the honest parties that aren't there for the attacker, for example, the CRT optimization on the private operation, and short exponents on the public one [1]

• The attacker has to run his operation on a Quantum Computer, which will likely be a large constant times as expensive as a classical one.

On the other hand, both these advantages don't add up to enough (especially given that we also assume the adversary has considerably more computational resources at his disposal than we do).

---

[1]: I believe that, when targeting a discrete log problem, Shor's can take advantage of knowledge that the exponent is small, and so that discrete log optimization doesn't help us.

Answer 2

The main reason is because any such technique has at best a polynomial gap between

1. the effort honest parties must spend to compute the cryptosystem, and
2. the effort adversaries must spend to break the cryptosystem.

Cryptography from a polynomial honest-to-malicious hardness gap has been known for a while. In fact, one of the earliest public-key cryptosystems (before RSA by a few years iirc) went by the name of Merkle's Puzzles, and had precisely this property, namely they took $O(n)$ time to compute for honest parties, and $\Omega(n^2)$ for adversaries. See Public-Key Cryptography in the Fine-Grained Setting for example. Moreover, in the random oracle model, this is size of gap is known to be optimal, at least in the classical setting.

This is to say that if you are going to "settle" for a small gap between honest parties and adversaries, it is perhaps better to do other things than simply RSA "scaled up" appropriately, though perhaps it is best to simply use a lattice-based scheme instead.

Answer 3

That's what CNSA 1.0 did: minimum RSA key length is 3072, minimum AES key length is 256, and minimum SHA length is 384. CNSA 2.0 goes beyond that with some new algorithms.