How can we reliably know if a key size is still safe to use as new quantum computers are created?

Question

I've heard that quantum computers pose a major threat to 1024 bit and possibly even 2048 bit RSA public-private key cryptography. In the future however, bigger size keys will probably become at risk at one point or another, as newer, faster quantum computers are created, for lots of (if not, all) algorithms. How can I reliably know if a key size, or even an algorithm itself is secure and safe to use at the current time? Is there a reliable resource/website that calculates which key sizes are currently at risk, based on how fast the newest quantum computers are? Or possibly, will new algorithms be created which try to prevent quantum computers from being able to crack them easily? The goal here is to keep the UX positive by not making a product slow due to encryption, but slower apps are worth it to guarantee a safe transfer of data.

Answer 1

We (i.e. the current state of research) just don't know, but we can guess.

We guess that there may be a problem if Post Quantum Crypto (PQC) lags behind, as Shor's algorithm can solve the factoring problem efficiently (thereby breaking RSA public key crypto) or for Grover's algorithm to force a doubling of the number of bits for all keys, as it can search a keyspace of $n$ bits in $O(2^{n/2})$ time (proportional to the square root of the size of the space of all possible keys), instead of expected $O(2^n)$ for the classical brute force algorithm.

So, PQC tries to create cryptography based on methods for which we currently think that quantum computing offers little advantage, such as lattice based or coding based crypto. But we can't know this for certain, just as we don't know whether there are classical algorithms that break current 'commercial grade' crypto.

Note that for RSA, increasing the key size simply doesn't work, as Shor can factor in time of a rather low order polynomial to crack the key. In other words, a key big enough for Shor to fail, is a key big enough such that any normal en/decryption operations are impossible.

So, we really need replacements. Fortunately, I think that PQC started on time and that we will get a good replacement for RSA (and others!) when the truly powerful machines capable of running Shor and Grover effectively arrive.

Answer 2

Given that you mention large key sizes (1024 bit and up), you are talking about asymmetric cryptography. Other (symmetric) cryptographic schemes are safe by simply doubling their key size (e.g. going from 128 to 256 bits) because that compensates for the theoretical advantage of Grover's algorithm for an exhaustive search.

Asymmetric cryptography can be divided into currently used, practical schemes (essentially RSA and ECC) and postquantum cryptography.

Since Shor's algorithm scales (in runtime) as $O(n^3)$, once a certain key size of RSA or ECC is unsafe, even doubling its size will only mean an 8-fold increase in the computational difficulty to calculate the new private key with a quantum computer: Once you conclude that RSA and ECC keys are no longer safe due to quantum computers, going to longer key lengths will not gain much. New algorithms ("postquantum cryptography") are being designed that are believed to be safe against attacks using quantum computers.

Postquantum cryptography already takes quantum computers as attack vectors into account. They typically require huge key sizes, though (such as more than 10 kbits).

Answer 3

Is there a reliable resource/website that calculates which key sizes are currently at risk, based on how fast the newest quantum computers are?

As other answers have conveyed, if a given algorithm is susceptible to attack by quantum computers, it's not really a question of going to a larger key length; it wouldn't take much technological advancement to bring that larger key length under threat (and you never really know what the current state of the art is). We've seen from the history of classical computers (e.g. Moore's Law) that once you pass some basic threshold, exponential improvements are possible.

What other answers haven't mentioned is timeliness. Yes, you could ask "based on our current state of technology, is a particular algorithm & key length combination secure?", but that is only an instantaneous security. Sometimes that's good enough. If you want to agree a clandestine meeting with someone tomorrow, and so long as nobody finds out about it until after the fact, that's fine, you can use any algorithm that gave a yes answer to the question. However, what if that information is to remain secret for longer? Perhaps you're emailing someone the identity of an under-cover agent they are to meet. It's not good enough that the identity of that individual is protected now, but it must also be protected going into the future. Any data like that, you essentially have to assume that if it has been encrypted with an algorithm that is potentially susceptible to attack by a quantum computer, it will be read at some point, and is therefore compromised. Actually, if you're super-paranoid, you should assume this about all crypto algorithms anyway because even if the theory says they're perfectly secure, their practical implementation may be faulty and susceptible to cracking.

Or possibly, will new algorithms be created which try to prevent quantum computers from being able to crack them easily?

To replace these potentially breakable systems, you need new methods, which generally come under the banner of post-quantum crypto. Some of these exist already, but there are varying levels of confidence about how well they will actually hold up to attack. Much like with factoring numbers on a classical computer, where the difficulty was essentially based on "lots of people have tried, and nobody's succeeded in doing it efficiently, so we guess it isn't possible", the argument is similar, but not so many people have tried, and not for so long, as to have a huge weight of confidence yet, although the aim is to back it up with a bit more rigour from CS, making connections to complexity classes, and particularly the assumption P$\neq$NP.