Post-Quantum Cryptography: A Q&A With NIST’s Matt Scholl

Quantum computing algorithms seek to use quantum phenomena to perform certain types of calculations much more efficiently than today’s classical, binary, transistor-based computers can. If and when a powerful enough quantum computer is built, it could run algorithms that would break many of the encryption codes we use to protect our data. In this interview with Taking Measure, Matt Scholl, chief of the Computer Security Division at the National Institute of Standards and Technology (NIST), discusses how worried we should be about this and what’s being done to mitigate the danger a future quantum computer poses to our data.

How is our information protected today? What would happen if a quantum computer were developed now?

One of the tools used widely to protect data today is called asymmetric encryption. This is the type of encryption that we use when you do a credit card purchase or have an online transaction with a bank.

This encryption system is easy for a classical computer to implement, but because of how searches are done in today’s computers, it makes it almost impossible to reverse-engineer it and undo it with our current machines.

Now, suppose a quantum machine that's strong enough to break these keys were built by an adversary today. It would most certainly be built by a nation-state. It would be expensive to operate and difficult to maintain, and they would use it to try to reverse-engineer and break into our most sensitive national security secrets.

So, the first question is, what information are we sending across networks that we don't fully control? How long are we going to have to keep that information secret? If you think about it, it's not just about the secret I need to keep today, it's how long does that information I've encrypted need to stay secret.

Imagine I send you a message that's top secret, and I've encrypted it using this type of encryption, and that message is going to need to stay top secret for the next 20 years. We're betting that an adversary a) hasn’t captured that message somehow as we sent it over the internet, b) hasn’t stored that message, and c) between today and 20 years from now will not have developed a quantum machine that could break it. This is what's called the store-and-break threat.

But this is not like the Y2K computer glitch where we have to worry that the day a quantum computer is built all of our encryption keys turn to dust and all the machines explode. For Y2K, this computer failure was supposed to be total and all simultaneous at the same time, midnight.

Rather than breaking an entire class of encryption in total and all at the same time, an adversary would have to collect that encrypted information and then apply the quantum capability against that single session of communication, break that, and then move to the next one.

We don’t anticipate talking about your personal bank accounts at first, but rather very valuable information that will be worth the expense of using those first cryptographically capable quantum machines, national security information as an example. That's why, even though there's not a cryptographically relevant quantum machine now, we need to be preparing now so that even the data we have today is quantum proof tomorrow.

Post-Quantum Cryptography: the Good, the Bad, and the Powerful

What is NIST doing to help prepare us for quantum computers?

We’ve been working on this issue since 2015 when, after soliciting feedback from the cryptographic community, we decided to identify and standardize new encryption algorithms to replace the ones that a quantum machine could break.

This is a tricky thing that hasn’t been done before, but we're well on our way to having new quantum-proof encryption algorithms that will work with our current binary machines. The algorithms we’re working to standardize will need to be deployed in our current technologies, protect our current information, and yet that encryption will still stand up to a cryptographically relevant quantum machine if, at some point in the future, one gets built.

We started with an open call for proposals and for algorithm submissions in 2016. It was then that NIST published the criteria for the encryption and how the public should submit a candidate algorithm. We spelled out the mathematical properties and the security capabilities we're looking for, the performance capabilities we desire, and the different types of use cases we need to apply, as well as how we're going to test and vet and make decisions and determinations.

We got an initial 69 viable submissions that came from all over the world.

We've winnowed it down by conducting cryptanalysis: breaking some of the algorithms, looking at how efficiently the code could be executed, understanding how well they operate in our current machines. We operate transparently. We’ve shown all our work and ensured that there’s traceability so that folks can see from the last selection round all the way back to what we selected, why and when. We’re now down to eight final candidates, and soon we will announce the first set of quantum-resistant encryption algorithms that we will standardize.

I say first set because we plan to continue to work on this over many years, to identify other potential new ones and to make sure we've got a strong backup library, because we still don't know the full extent of what might emerge in quantum science and quantum mathematics, as well as ensuring that we continue to update and refine the standard.

It's a public, participative process with teams from industry, academia, standards bodies and other countries working with us and electing to follow what NIST standardizes.

What can companies and people do now to protect themselves from future attacks?

If you're an organization, don't wait for the standard to be done. Start inventorying your most important information. Ask yourself what is that data that an adversary is going to want to break into first. Because again, the first quantum computers are going to be expensive to operate and maintain, so determine what is your most important information and whether its encryption is vulnerable. If it is, then develop priorities for using quantum-resistant encryption as you plan to upgrade your infrastructures over the next couple of years. And then start to prioritize and plan so that you're ready to implement the new standards when they are available.

For those of us in the consumer space, we're going to rely on our tech providers to roll this out for us. Our IT product and service providers are ready, and they're itching to get these new standards out there and put them to work.

*Edited October 27, 2021