[00:25] Quantum Computing

Petko: Today we're joined by Dustin Moody, a mathematician from NIST computer security division. We're going to talk about a topic that has the potential to change our lives. Like the internet got invented decades ago, this topic has the ability to change how our computers talk.

We're talking about quantum computing. Dustin, thank you for joining us today. We've all heard quantum before. What is quantum computing or how could it potentially change, and what are we worried about?

Dustin: Quantum computers, they will bring forth a lot of different possibilities, most of them very great applications. It would be a lot of benefit to our society. So at their core, quantum computers are built using principles of quantum physics. That's often different than a lot of the physics that most of us learn back in high school.

These quantum physics has some pretty counterintuitive properties that they're able to exploit in these computers. It leads to a potential huge increase in computational power for lots of different algorithms and lots of solving different problems.

Quantum computers won't completely replace all the computers we have today because they don't do everything better. But there are certain things that they will do a whole lot better. We'll be able to design better medicines. We'll solve complicated logistics problems, be able to come up with improved weather forecasting, for example.

The reason it's of interest to me and my area of focus is that quantum computers also have the capability to do something destructive besides all this positive applications. Namely, they pose a threat to a lot of the cryptosystems that we use today.

 

Quantum Computing and Cryptosystems

Petko: What do you mean by cryptosystems? Let's elaborate on that a little bit more.

Dustin: Sure. So all of us, when we go online and we want to send information in an email, we hope that it's encrypted. This is so that what we're saying is not open for just anybody to see it as it goes over the line.

If you're going online and you want to buy something using your credit card or do some banking transactions, cryptography is used behind the scenes by your browser to protect all of those transaction and encrypt all that information. 

The cryptography we use today, there's various different types that get used. There's what's called public key cryptography. That's where you and the other party that you're going to be communicating with.

You don't already have a shared key established, and you'll typically use public key cryptography to create a shared key, and then you'll use that shared key and switch over to a faster algorithm called AES.

Public key cryptography is also used to do what are called digital signatures. And like what it sounds like, that's like an electronic version of your handwritten signature. It authenticates something. So if you have a document and you put a digital signature on it, somebody can come by later. Using your public key, they can verify that you are the author of that document.

So those are some of the cryptosystems that we use today, and most of us don't even think about them. They're all just being used behind the scenes, but we rely on them crucially. We only typically hear about them when there's been some hack or a breach or something like that.

 

Quantum Computing and Cryptosystem Threats

Petko: I just want to draw into this a little bit more because when you said crypto, my mind went two different ways. One is cryptography and the other is Bitcoin. So just to make sure I understand. Two sides of it, one is the cryptography side where our communication could be impacted from a privacy standpoint or even someone could pretend to be us by changing, as you said, digital signatures.

Our minds automatically go to the bad. Has quantum computing matured enough today that we have nation states or folks who have the means or the computing capability to break that encryption today?

Dustin: Before I answer that, you mentioned cryptocurrency. Yes, the word crypto's in there. Cryptocurrency does use cryptographic algorithms, but that's kind of not what we're talking about as the main focus. They will need to update those cryptographic algorithms in Bitcoin and other things. 

But more to your point, has quantum computing progressed enough that it threatens cryptography? The answer is yes and no. I'd say no, because the computers that are being built by companies like Google and IBM, they put out press releases. Those computers are not yet big enough that they threaten cryptography or come close to it.

It's still estimated that that's probably a decade, 15 years, something like that before we have large enough quantum computers that would threaten current levels of cryptography. But I also say yes, they do threaten it because you can already be at risk from a future quantum attack even though one hasn't yet been built.

 

 

[05:39] Post-Quantum Cryptography

Dustin: Imagine you've got your data encrypted somewhere and maybe it's stored online in the cloud or something, and you've got an adversary or an enemy who gets a hold of that data. At first you think, well, that's fine, it's encrypted. He can't read it, that's true. Maybe he waits 10 years until the quantum computer comes out and he's able to get access to that data.

Now, what if those are information there that's supposed to be protected for 30 years or something? Then he's getting access to the data before you wanted them to be able to do so. You can be at risk today from a quantum computer that's not yet built. That's why this is of concern even though we're still potentially 10, 15 years out before a big enough one is built.

Petko: Now, I believe, are we working on, a follow-on encryption that is more, post-quantum or less likely get decrypted from quantum? Is there a different encryption method that would help ensure that we're secure, we have the right digital signatures that is available today or will be available in near future?

Dustin: Yes. That's what our team at NIST and cryptographers around the world have been working on. This field is often called post-quantum cryptography. The goal is to replace those algorithms that would be vulnerable to a future quantum computer with new ones. These new algorithms will still be classical.

They'll still run on classical computers. They'll be implemented in software and in hardware, but they are believed to be resistant to attacks from quantum computers. That's the idea there. It is coming out with new cryptographic algorithms that will protect against both classical attacks and quantum attacks.

 

Post-Quantum Cryptography: Competition of Algorithms

Petko: So you said it's out now already or it'll be out soon?

Dustin: Yes, so researchers have been studying this problem for a couple of decades. At NIST we make cryptographic standards in order to start taking some more concrete steps towards standardization. It is needed before these algorithms can be adopted. In 2016, we announced that we would be doing basically a large international competition to find and select new post-quantum algorithms.

And so that process has been going on since then. Design teams around the world composed of researchers from academia and industry came out with their best solutions. They sent them in. We had 69 different algorithms that were accepted into the process, so there was a big number. And this was an open, transparent proceedings. We posted all of the specifications online. We put the code online, so people could test them out and they could experiment with them. They could try and find attacks for them.

And we've gone through five or six years now of evaluating them. We did this kind of in a series of rounds. At the end of each round we would pick the most promising ones. We would kill off the ones that had been broken or attacked. Then move the good ones into the next round.

So where we are today is after three rounds of evaluation and analysis. Just a few months back, we announced the ones that we selected that these are going to be the algorithms that people are going to be adopting into the future. That was a pretty big milestone for our project. It is good news for protecting against these future quantum attacks.

 

Post-Quantum Cryptography: Establishing Standards and Product Control

Petko: So NIST makes the standards that we all use, AES and lots of encryption. What's the status of rolling out some of these post-quantum candidates into products or government entities or just for trying them out? I'm worried that 10 years from now, it reminds me of Y2K 20 years ago, we had this massive push literally in 1999. “Let's go ahead and upgrade all of our clocks because if not, come 2000 where everything's going to crash.” 

I feel like we almost have a Y2K moment with some of this quantum eventually. It might be a little more fuzzy in terms of the date. But I'm really interested in the rollout of how can we get to this level of security. Last year, I think President Biden signed the Quantum Computing Cybersecurity Prepared Act and he talked about rolling that out. What does that look like in terms of rolling out some of these algorithms?

Dustin: Yes, that's where the focus is on right now. Now that the algorithms have been selected, at NIST, we're writing up them into standards. We expect in a few months to put out drafts of the standards for public feedback. We'll make any changes, and we expect that they should be published in 2024 sometime.

Up until then, we don't recommend people start baking this into products. Certainly you can test them out, you can see how they will work for your applications. But because small changes could still be made before the final standard is published, and we want you to be interoperable, we recommend just holding off on rolling that out at this point. So what the focus on is largely as making sure that you are aware of this transition and starting to plan and prepare for it.

 

Post-Quantum Cryptography: Transition Plan and Preparations

Dustin: Some of that guidance has been given out, as you were noting. The Biden administration in the White House put out two national security memos that were focused on post-quantum computers. The OMB kind of got a little bit more detailed.

They gave some more detailed guidance with timelines to federal agencies making sure that this was on their radar. OMB is going to be publishing reports every year. Agencies need to be reporting back their progress and their plans. 

And then most recently, the Quantum Cybersecurity Preparedness Act was passed by Congress and signed into law just in December. It didn't really have a lot of new requirements that hadn't been mentioned in these earlier memos in the OMB guidance. But it's good to see that the federal government is taking this seriously and making sure that agencies are aware and planning and preparing, and we know that industry is also going to follow suit.

They provide a lot of the products that the federal government uses. They've been participating in this process the whole way.

So yes, the transition is slowly going to be starting. It's going to take a little while. We certainly expect that it'll not happen as quickly as we hope. But yes, that's kind of the goal. Some of these documents pointed to a date of 2035. They're hoping that as many federal government systems can migrate by 2035, that's kind of the target date that they're hoping for.

 

 

[12:14] Quantum Computing and Data Protection

Petko: Now, since you're a researcher at NIST, are there any suggestions that organizations should do while we wait for the quantum encryption to be standardized? I mean, I can't help but think negatively, but also can see all the huge benefits from quantum. Are there any suggestions around what organizations should do to protect their data or that they are worried about?

Like you mentioned, someone could hack now and decrypt later. Is there something we can do to maybe protect an organization or protect an individual or protect the government agency?

Dustin: Yes. So there are things you can do to protect the data that you have now as well as to prepare for this transition. First, make sure you're using strong cryptography. Even though we will be transitioning to these new algorithms, that's not an excuse to not be using the state-of-the-art cryptography and best practice right now, so be using high-security levels. 

In terms of the transition, what you should be looking for is you should be inventorying what cryptography that you have in your products, what cryptography is in your vendor, what's in your system. Are these cryptosystems public key algorithms or are they symmetric key algorithms? 

The symmetric key algorithms, they do provide protection against quantum computers. We're going to have to use longer keys, which is doable. We don't have to completely replace the algorithms though. So like for AES, you want to be using AES-256, but that's fine. We have implementations of that around it's a pretty efficient algorithm.

 

Quantum Computing: Implementation

Dustin: You want to look for where you're using public key cryptography in particular, and look at how easy is that going to be to remove. This transition will be coming. Public key cryptosystems have larger public keys, they have larger cipher texts, larger signatures. Will your applications be able to handle that? Will the protocols you use?

Does your IT staff know about this? Are they tracking this? They can start experimenting with the algorithms. 

The code is out there, there are implementations out there to see if they'll work. Do you have someone who's in charge of your plan for your organization? We really recommend you don't wait for the standards to plan and prepare for this, that you have people mapping out, once the standard's there, what's our next steps? How are we going to transition to these?

That's going to be a difficult, costly process. So the sooner you start planning for it now, the better it will be for you.

Petko: You mentioned something unique. We think of quantum as it breaks all encryption, but you pointed out that symmetric is still potentially protected. Is that correct? And it's the public ones that are of concern. Just for examples, what are public and what are symmetric from a user standpoint?

Dustin: Yes. Quantum computers, let me be clear, don’t break all the encryption algorithms that we have today. They break what are called the public key cryptography cryptosystems. This includes algorithms like RSA, Diffie-Hellman and elliptic-curve cryptography. These algorithms are typically used to do one of two things.

You're going to establish a shared key. You're then going to use that shared key and switch over to a symmetric key algorithm like AES, or you're going to use them to do a digital signature.

 

Quantum Computing: Encryption

Dustin: So it's the public key algorithms that are vulnerable. Those are the ones that we are getting replacements for. The symmetric key side, those are algorithms where you have a shared key already pre-established.

We also typically lump hash functions into symmetric key cryptography, even though they don't have a key. We use hash functions like SHA-2 and SHA-3 all the time. Those algorithms do not need to be replaced. What we need to do is use a longer key or a longer hash output.

So AES-128, if you double the key size to AES-256, you will provide it at least as much protection as you were with AES-28. You may not even need to go all the way up to AES-256, but it certainly doesn't hurt you, and that would be a prudent thing to do. For hash functions, similarly, you'd want to double the output length. So if you were using SHA-256, you might want to consider using SHA-512, then the output length is doubled. And that will protect you against quantum attacks on the symmetric key side.

Petko: That's a good thing to hear because, you kind of think encryption gets broken with quantum. So if someone does potentially hack your system today and your data is encrypted with AES-256, they're still going to struggle, even if they have quantum, to decrypt it.

Dustin: Yes, that is true. And most data at rest is encrypted with a block cipher with AES. So you're in good shape there. You'd want to be concerned if you were using AES-128 because that could still potentially be vulnerable to a big enough quantum computer in the future. 

 

Quantum Computing: Ideals and Positives

Dustin: The first quantum computers won't be strong enough to attack that. But then you also have to look at, well, where's the key for that AES block cipher? Was it established using public key means or some other way? So you still need to be careful and look at where are all the potential vulnerabilities, although using AES should protect you.

Petko: Okay, so the key exchange, if I potentially shared my key over public key encryption, I've got to make sure I rotate it as well, it sounds like. So I can't be, if they hear it two years from now, that key should have changed by now hopefully.

Dustin: Yes. That would be ideal. In cryptography, there's a lot of ideals that we hope industry are following, but we know that that's not always the case. There's still people out there using algorithms that have been broken 10 years ago, so.

Petko: I'd love to get your take on, you mentioned some of the positives from quantum. Can you talk more about some of the benefits we could see from quantum? I know we've got a 10 years out probably for it, but some of the items you mentioned are really interesting in terms of the benefits society could see.

Dustin: Yes, and that's why researchers and companies are working so heavily on this because these positive applications will be a huge benefit to society and science in general. And I'm not kind of the expert on what they are exactly off the top of my head, but I do know that there are quantum algorithms that will improve modeling for designing drugs.

That's one application. 

 

 

[18:39] Quantum Computers vs. Classical Computers

Petko: You said weather models. We know our weatherman's always correct and our weather's accurate down to the individual, but I think having more faster computers that could potentially factor in more options. Maybe we talk about how quantum's kind of different from the regular computer. Can you highlight that?

Dustin: Yes, so quantum computers, here's kind of a property that helps you understand how they're a little bit different than the classical computers we have. So in our current computing technology, all information eventually gets broken down into zeros and ones. We've got bits, and inside your computer, it's binary.

A switch is either flipped or it's not. 

Quantum computers use what are called quantum bits to represent quantum states. And the interesting thing that they're able to do is you're able to put these quantum states in a state called superposition where a quantum bit, or what's called a qubit, it can actually hold a zero and a one quantum state at the same time simultaneously, which we can't do with a classical computer. It just doesn't work.

Now, if you imagine now that you string together, say, 20 of these qubits and put them all in superposition together, the first qubit can hold a zero and a one. The second qubit can hold a zero and a one. If you count kind of the total number of states that those 20 qubits are holding, it's actually two to the 20 states, which is quite a large number. Classical computer, if you have 20 bits, you hold one string, it's just one state. 

 

Quantum Computational Power

Dustin: Now imagine you design an algorithm that is able to interact with these 20 qubits. Naively, you can kind of think of this as it will do a computation on two to the 20 different states in a parallel fashion with just one running through of the algorithm. And that's why there's this potentially huge kind of computational power that comes, because these qubits are representing more than one state.

And if you have a quantum computer that has hundreds or thousands of qubits and you've got your algorithm designed to manage that, then an appropriate quantum algorithm will do things way faster than a classical computer.

One example of this is what's called Shor's algorithm. So our public key cryptosystems today, there's one called RSA, that for its security, it depends on that it's hard to factor an integer into its prime factors. So for example, 35 is five times seven. We can do that in our head. But RSA uses key sizes that are hundreds of decimal digits long, and the most powerful computers that we have today using the best-known factoring algorithms can't factor that key into two prime factors. 

Well, Shor's algorithm gives an exponential speed up, and if you have a quantum computer that'll have roughly around 3000 logical qubits, it'll be able to crack RSA at current security levels in less than a day. Whereas today's most powerful supercomputers, it's intractable. They can't break it after hundreds of years.

So that's kind of the idea of why quantum computers are so powerful, is they exploit these properties of entanglement and superposition to do weird things that just our classical computers cannot do by nature.

 

 

[22:15] The Promise of Quantum Computing

Petko: Just to dumb it down and make sure I understand what you said. So in this superposition standpoint, I'm running both the zero and the one simultaneously. If I have a string of them, it's almost like I'll use my phone. I have a certain pin for it to log in. In a hypothetical standpoint, I might have six digits. It's like trying all six digits with every possible option at the exact same time with one command.

Dustin: Yes, that's the intuition. That's the right idea. It can do all of that with one step. With a classical computer, it has to go through each one, one at a time.

Petko: I can see how that your first instance is that could break encryption, but then at the same time for drug modeling and just tracking anything that requires multiple options that have to be considered, or variables, you could literally do it in milliseconds instead of years.

Dustin: That's the promise of it. Now, it's got that great promise and we don't yet have these computers and there's a lot of difficulties in building them. Putting these particles in quantum states, they're usually able to get them to only last for very small amounts of time. They have to work with them in temperatures near absolute zero and in vacuums. And these are engineering challenges that they're working on, and that we believe that they will overcome these challenges, but it is very, very difficult thing to do.

Petko: I think I recently read in the news that there was an article that China had potentially broken that barrier. It was with something as low as a 10 qubit quantum computer. Instead of requiring a 2000 or 3000 qubits, they did with 10 to crack RSA 48-bit.

 

The Quantum Computing Race

Dustin: Well, Yes. So there was a story a couple weeks ago right after the new year that some Chinese researchers published a paper. It got a lot of buzz. They were claiming that their technique could eventually, if extended, break RSA-2048, which we use today. That paper seems to be a little bit more hype. It does not actually break RSA-2048, and speaking with several experts and diving into the details, it potentially is a promising technique, but in practical terms, it doesn't.

There was nothing shown that it would offer any speedups to any known algorithms that attack RSA. So China does have a lot of very smart people. They're definitely spending a lot of money to develop quantum computers and quantum technologies. That's something that we certainly need to be aware of.

Petko: Is there like an arms race going on between quantum on a global scale, it feels like?

Dustin: Yes, I'm not a high government official who speaks on policy, but it's very clear that China is spending a lot of money. There's another technology related to quantum computers and cryptography called quantum key distribution. China's invested heavily in this technology.

They've even launched a satellite that can do QKD from a satellite to the ground on Earth. So yes, there is various countries that are trying to be the first to develop a quantum computer. I don't know if we'll know who is the first. I don't think that they will announce to the world, "We have a quantum computer." Probably, whoever gets it first will be using it to try and attack their enemy's communications.

Petko: Interesting. Hopefully, whoever gets it first uses it for good rather than evil.

 

Quantum Computing and NIST

Dustin: Yes. So companies like Google and Microsoft and IBM, and there's several others that are building these. They are being quite public with the advances that they're making. They publish papers and reports. I believe their intention is to enable people to access them and do these positive applications that we hope for.

Petko: Dustin, thank you. I've learned so much about quantum today. Hopefully our audience has as well, and the positives and negatives that we'll see in the near future. Is there anything else we want to share with our audience?

Dustin: Yes, so if people in industry or other organizations want to get a little bit more guidance on this transition, NIST has what's called the National Cybersecurity Center of Excellence that's running a project on the PQC migration, and it has a lot of good information.

So if you just search for that on the internet, you'll easily find that project. And at NIST, we're always happy to talk to you as well if you need more information on post-quantum cryptography and standardization. But I think that's all that I can think of.

Petko: Awesome. We'll make sure we include that link in the show notes for the audience and direct everyone to you. Dustin, thank you so much today for taking time to educate us. And thank you for supporting the mission and keeping us honest and fighting the good fight in quantum worldwide. So thank you.

 

About Our Guest

 

Dustin Moody is a mathematician in the NIST Computer Security Division. He leads the post-quantum cryptography project at NIST. He received his Ph.D. from the University of Washington in 2009. His area of research deals with elliptic curves and their applications in cryptography.