- Nolan Hedglin

# The temporal aspect of breaking encryption with a quantum computer

You've probably heard someone claim before that a *sufficiently* *large *quantum computer will be able to break a *sufficiently weak *encryption standard within the next few decades. And this is perfectly true in theory, but in practice it requires a large number of assumptions.

## When is a quantum computer a threat to encryption?

To begin, we need to define what we mean by "breaking encryption." Does it mean being able to decrypt just one message? I could start guessing 1024-bit primes at random until I get lucky and find one that decrypts an RSA-encrypted message, but that doesn't mean I've broken RSA-1024. There are still a myriad of other messages that I haven't been able to decrypt. Additionally, each one will take a random amount of time to decrypt because their prime factors are generated in a pseudorandom manner. So what we actually mean by "a quantum computer will break existing encryption" is "a quantum computer will, on average, decrypt messages within a short amount of time."

But now we need to define what qualifies as a short amount of time. Days? Hours? Minutes? This question does not have a single answer because it depends on how that encrypted information is being used. For example, suppose I send a WhatsApp message to my friend that says, "I am leaving the house now and won't be back for 4 hours." If Eve is a quantum-capable burglar intent on robbing my house, then she would need a computer large enough to decrypt that message (assuming she intercepts it) in less than 4 hours or else she will miss her window of opportunity. This is in stark contrast to information that may be sensitive for decades, such as the blueprints for the F-35. Let's call this quantity *information lifetime.* In this scenario, the information lifetime of the message I send my friend is 4 hours. This brings us to the main point: **Eve's quantum computer is only a threat to encryption if the average time it takes her to decrypt a given message is less than the information lifetime for that message**.

## How large does a quantum computer need to be?

Now let's talk about the average time it takes to decrypt a message. Shown in Table 4.1, the National Academies of Sciences __published a report in 2018__ on the average time it takes to decrypt a number of commonly used algorithms.

The first thing that sticks out to me is how large the number of logical qubits needs to be in order to break an RSA-encrypted message within hours. For reference, the largest quantum computers today are near 80ish qubits. We are clearly still at least several decades away from reaching a point where even RSA-4096 is no longer secure for daily communications.

The second thing that sticks out to me are the footnotes. The numbers presented in this table come with quite a few assumptions nested as footnotes in the report (as shown below).

As you can see, it is not easy to calculate the average time it takes to decrypt a message, even if we know exactly how both the encryption and decryption algorithms work (for a layperson's primer on Shor's algorithm, check out __this blog post__ from Scott Aaronson). The authors of the report had to make a lot of assumptions about how they think quantum computers in the decades to come, which is always subject to change as new architectures and error-correction codes are developed.

## When should we start worrying?

My hope is that, after reading this post, you are convinced that there will not be a defined moment when quantum computing breaks classical encryption. It will be more like an ocean tide slowly coming in than like a tsunami. Nevertheless, we should transition to quantum-resistant encryption as soon as possible for a couple reasons. First, there is information stored right now that may remain sensitive for the next 50 years, so it will be still be vulnerable to a quantum computer unless it is re-encrypted. Second, the shift from one Internet encryption standard to another __may take as along as 20-30 years__. Internet standards move slowly because it requires a lot of inertia to change the status quo. Luckily, recognizing this challenge, __NIST has been working on the problem__ of quantum-proofing the Internet for some time now. So there is no need to panic unless we make zero progress on this front for the next couple decades.