• 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.

19 views0 comments

Recent Posts

See All