Become a Creator today!Start creating today - Share your story with the world!
Start for free
00:00:00
00:00:01
What is Cryptography?
0 Playsin 5 hours
This conversation delves into the intersection of quantum computing and cryptography, focusing on the implications of quantum computers for current encryption methods and the necessity for post-quantum cryptography. Dr. Dustin Moody from NIST discusses the threats posed by quantum computing, particularly through Shor's algorithm, and the ongoing efforts to develop new cryptographic standards that can withstand these threats. The discussion also covers the role of NIST in standardizing post-quantum algorithms, the mathematical challenges involved, and the importance of preparing businesses for the transition to these new systems.
All opinions are of the individual scientist and do not reflect the opinions of NIST or the federal Government.
Takeaways
- Quantum computers harness principles of quantum physics for computation.
- Shor's algorithm can efficiently factor large numbers, threatening RSA encryption.
- Post-quantum cryptography aims to develop algorithms resistant to quantum attacks.
- NIST is leading the effort to standardize post-quantum cryptographic algorithms.
- Lattice-based algorithms are promising for post-quantum cryptography due to their efficiency.
- Businesses must be proactive in transitioning to post-quantum cryptography.
- The Harvest Now, Decrypt Later threat highlights the urgency of transitioning.
- Quantum key distribution offers theoretically perfect security.
- Different cryptographic algorithms are needed for various applications and devices.
- The future of cryptography will rely on new mathematical challenges to ensure security.
Keywords
quantum computing, cryptography, post-quantum cryptography, NIST, cybersecurity, Shor's algorithm, digital signatures, lattice-based algorithms, encryption, quantum threats
Subscribe to Breaking Math wherever you get your podcasts.
Become a patron of Breaking Math for as little as a buck a month
Follow Breaking Math on Twitter, Instagram, LinkedIn, Website, YouTube, TikTok
Follow Autumn on Twitter and Instagram
Become a guest here
email: breakingmathpodcast@gmail.com
Recommended
Transcript
Introduction to Quantum Computing and Cryptography
00:00:00
Speaker
Welcome to this episode of Breaking Math, where we explore the fascinating intersection of mathematics, technology, and the future of cybersecurity. I'm your host, Gabriel Hesch, and I'm joined by my illustrious co-host, Autumn Faneff.
00:00:10
Speaker
Today, we dive deep into one of the most critical challenges facing our digital world, the advent of quantum computing and its profound implications for cryptography. Quantum computers, with their potential to solve problems far beyond the reach of classical systems, are seeking innovation.
00:00:24
Speaker
However, they also pose a substantial threat to the crypto to the cryptographic systems that secure our most sensitive information, from financial transactions to national security data. The National Institute of Standards and Technology, NIST, has taken a leading role in addressing these concerns through its Post-Quantum Cryptography, PQC, project, developing encryption algorithms designed to protect against quantum attacks.
00:00:47
Speaker
To guide us through this complex and highly important topic, we are joined today by Dr. Dustin Moody, a mathematician in the NIST Computer Security Division and the lead of NIST's Post-Quantum Cryptography Project.
00:00:58
Speaker
Dr. Moody holds a PhD from the University of Washington where his research focused on elliptic curves and their applications in cryptography.
Dr. Dustin Moody's Journey into Cryptography
00:01:05
Speaker
Under his leadership, the PQC project is driving the global effort to standardize cryptographic methods that will ensure our data remains secure in the quantum age.
00:01:14
Speaker
We'll be discussing everything from the technical challenges quantum computers present to modern cryptography to NIST's ongoing work in developing the algorithms that will safeguard future information systems. Stay tuned as we explore what organizations and governments need to do today to prepare for this next quantum leap in technology. Hi, Dustin. How are you doing today?
00:01:32
Speaker
I'm doing great. How are you? Pretty good. Thank you for joining us today. So tell us a little bit about your background and the research that you do in cryptography. Yeah, so cryptography is a very fascinating subject. And my my route into cryptography came via mathematics.
00:01:50
Speaker
So I've always loved math since I was little. And in in college, I got my degree in math. And I specialized in an area that's called number theory. And even a subcategory of that's called elliptic curves.
00:02:03
Speaker
Turns out elliptic curves are used in many cryptosystems that we use today. And so that was kind of my connection where I started learning about cryptography.
Understanding Cryptography and Quantum Threats
00:02:12
Speaker
And then after I finished my degree, got my PhD, I ended up working at NIST, the National Institute of Standards and Technology,
00:02:20
Speaker
NIST does a variety of scientific things, but the area that I work in, NIST creates what are called cryptographic standards using some of the the mathematical techniques that I've learned. Having that math background got me into cryptography and that ended up at the job I'm at today. Super exciting. Now, how does cryptography work? Well, that's hard to give just a really short answer, but I can try and explain. um i think the easiest example most people have with cryptography is, you know, you've got a message that you want to share with your friend and you'll come up with some code and cipher the message in some way so that you're your friend knows how to decode it.
00:02:57
Speaker
But presumably, you know, if somebody were to chance upon that message, it would look like gobbledygook and they wouldn't know what was being said. So modern cryptography tries to do that in a very sophisticated way of scrambling your message. And some of the techniques that we used are based on different mathematical techniques that kind of have a hidden trap door in them.
00:03:20
Speaker
Meaning if you know some secret information, you can do a certain computation very, very easily. Whereas somebody who does not have that secret information, they can use all the computing power that they want, but it's not start good enough to to solve a particular problem.
00:03:37
Speaker
So using that kind of mathematical trapdoor, you can encrypt a message and then the person with that secret knowledge can decrypt it. And so that's that's kind of the the basic idea. And a simple example of a trapdoor that gets used today for a crypto system, there's what's called the RSA crypto system.
00:03:54
Speaker
It's really easy to multiply numbers. So if I told you, you know, multiply five times seven, you get 35. thirty five Reverse process is factoring. If you have a number, try and factor it into its prime factors. So the factors of 35 are five and seven.
00:04:10
Speaker
Now, it's easy to factor if you've got small numbers, but if you choose huge numbers that are hundreds of decimal digits long, turns out that's hard even for modern supercomputers to do in any reasonable amount of time.
00:04:22
Speaker
And there's a crypto system called RSA built entirely on that. With the ease with which you can multiply, you can easily encrypt, but only somebody who knows the the the secret factorization of a certain number is able to decrypt that message.
00:04:37
Speaker
So, That's kind of the idea you've got hidden trap doors that enable this kind of functionality that somebody can decrypt and nobody else can read the message. Now, I've always found that to be interesting, but I know that there's something called quantum computers as well.
00:04:54
Speaker
How does that Factor into cryptography and what makes quantum computers so powerful. They can break encryption methods that are used by conventional computers.
00:05:04
Speaker
Yeah, so quantum computers are a fascinating thing in their own right. They harness the principles of quantum physics to do some things that seem very counterintuitive or even impossible for classical computing technology. They leverage what's called the principle of superposition, where you're able to put quantum particles into a state of superposition where they're kind of occupying both a zero and a one state at the same time, which you can't do with a classical computer. A bit is either a zero or a one.
00:05:34
Speaker
At any rate, what this means is that quantum computers are going to give us some big breakthroughs in computational power for certain problems. And that's going to be great for society. There's a lot of positive benefits. We'll be able to design new drugs, more efficient batteries, solve complicated logistics problems because these quantum computers are are very powerful.
00:05:56
Speaker
But it's been known since the 1990s that they can also break a lot of the crypto systems that we use today. So that's kept cryptographers worried for the past few decades. on That crypto system that I explained, RSA, it's known that if if you have a big enough quantum computer, that it will be able to factor numbers efficiently and break
The Discrete Log Problem and Post-Quantum Cryptography
00:06:16
Speaker
RSA. So anyone relying on that would be vulnerable once we arrive at the era of when we have powerful quantum computers.
00:06:24
Speaker
What specific vulnerabilities does a quantum computer expose in these systems? So quantum computers, people have looked for what algorithms will be able to run on them.
00:06:35
Speaker
And there's one specifically known as Shor's algorithm that is really relevant for cryptography. And what Schwarz's algorithm does as it looks at a function, like a mathematical function, and it tries to find the period.
00:06:49
Speaker
What that means is how often until the function repeats itself again. Certain mathematical functions, like the sine wave, they're periodic, they repeat, and Schwarz's algorithm can find in the period very, very rapidly.
00:07:02
Speaker
So somebody noticed, well, Peter Shore did, the guy that the algorithm was named after, that you can transform the factoring problem into a problem of finding the period of ah a related mathematical function.
00:07:16
Speaker
And so Shore's algorithm would be able to factor efficiently. Pretty interestingly, Shor's algorithm would also be able to solve another problem known as the discrete log problem. We don't have to go into the definition, but there are many other cryptosystems that we use today that are also rely on the discrete log problem being hard for conventional computers to solve.
00:07:36
Speaker
So it's fascinating that Shor's algorithm wipes out both those classes and it will essentially kill what's called public key cryptography, and which we very much use today. Now, just out of curiosity, can you give us a small definition on those two things? Certainly. So the discrete log problem, if you've had a little bit of math and you know what a group is, that's often studied in abstract algebra.
00:07:59
Speaker
So if you have an element, we'll say g that's in your group, and you multiply g by itself a ton of times, you'll you know you'll eventually get power you get powers of g. So let's say we multiply g by itself x times, and you end up with the element g to the x. So the discrete logarithm problem says if I simply give you g and I give you g to the x, you need to tell me what x is. And that's kind of the equivalent of finding a ah logarithm like we we learned back in high school, just done in the setting of an abstract group.
00:08:31
Speaker
And for cryptography, the groups we use are in finite fields as well as in elliptic curves defined over finite fields. So that's where a discrete log or the problem is relevant.
00:08:41
Speaker
So the other term I used was public key cryptography. So cryptosystems can broadly be broken down into two different categories. There's what's called public key cryptography and what's called symmetric key cryptography.
00:08:53
Speaker
Symmetric is a little bit easier to understand. That one is you and the person you're communicating with, you have already created or established a shared key that you both have and you both know. And using that shared key, it's very easy to encrypt and decrypt back and forth because you already have a shared key.
00:09:10
Speaker
Public key cryptography is a more modern invention. And it's it's pretty, pretty cool. It uses the idea that the person you're communicating with, they have a public key, or in other words, a key that they make public.
00:09:23
Speaker
Think of it as like their email address or a phone number, you know, some some public information that anybody can look up. they also have a private key that they keep secret. Now, if somebody wants to send them a message, they look up the public key and they can do a computation with that public key to encrypt a message to that person.
00:09:41
Speaker
And then that person will use the private key and they are able to decrypt it. So the way we use cryptography and in a modern system is we will typically will use public key cryptography initially and create a shared key between you and whoever you're communicating with.
00:09:56
Speaker
And then once you have that shared key, you can switch over to symmetric key cryptography, which is a whole lot faster. And so that's kind of the way we do things today. But out of curiosity, what is post-quantum cryptography and why is it necessary for the future of cybersecurity?
00:10:13
Speaker
All right. So I told you just a little bit ago how a quantum computer, once it's big enough, will threaten many of the crypto systems that we use today, specifically all the public key crypto systems that we use today.
00:10:24
Speaker
What we need to then do is come up with new crypto systems, which will still protect us even in the face of these quantum computers. And we might think we can just wait for a while and, you know, we'll solve this problem later once once quantum computers get big enough, because right now they're they're still too small.
00:10:39
Speaker
But it takes time to come up with new ideas. It takes time to, you know, evaluate them and have experts vet them so that we have confidence that we can then use them and put them into our applications.
00:10:50
Speaker
So the name of this kind of area of study is known as post-quantum cryptography or sometimes quantum-resistant cryptography or quantum-safe cryptography. It's looking for new cryptosystems to replace the ones that will be vulnerable.
00:11:04
Speaker
So these new these new algorithms will need to protect against quantum computers. they still They still also need to protect protect against classical conventional computers because those aren't going away. We'll still have them.
00:11:16
Speaker
And they'll run on conventional or classical computers. So
Current State and Future of Quantum Computing
00:11:20
Speaker
sometimes people think because the quantum computer is a threat, ah we need to implement the crypto system on a quantum computer or something.
00:11:27
Speaker
Well, that's not what's going to happen. you know Our laptops, our phones, all the devices we have are are not going to be quantum, at least not for a while. So we need these post-quantum algorithms to run on our classical computing technology, just provide us the protection against ah these quantum attacks of the future.
00:11:45
Speaker
Can you clarify the difference between post-quantum cryptography and quantum cryptography? Yes, they both have the words quantum and cryptography, so easy to confuse the two.
00:11:57
Speaker
Post-quantum cryptography is is what we're talking about tonight. It's it's finding cryptosystems which will run on classical computers that will protect us and our information in the future, i'm replacing the vulnerable algorithms of today.
00:12:11
Speaker
What quantum cryptography is, is using quantum technologies to build cryptographic systems or cryptographic algorithms. And it's actually a pretty fascinating area.
00:12:21
Speaker
There's a technique called quantum key distribution, where if you are able to set it up properly, you can actually encrypt a message or... or um establish a shared key with with the party you're communicating with using quantum technologies, using quantum devices in such a way that it's information theoretically secure, which is not something we can actually do with classical computers.
00:12:44
Speaker
What that means is you can send the information to that that person you're communicating with and anybody looking on, scientifically it's proven by the laws of physics that they gain no information by looking at it. It's a perfect system at hiding the message. Even if they have the most powerful machines, there's nothing you can do to to attack it.
00:13:06
Speaker
So that's that's really great, and it will be useful for some applications, but there are some limitations of quantum cryptography. First, you need to use these quantum technologies, these quantum devices, which are expensive, and they're not going to be what most people have.
00:13:20
Speaker
So it's not what we can use, you know, just on our our laptops or anything. Second, it's geographically limited. It turns out in order to implement this, you can do it over a fiber optic cable, but it only can go so far. Right now, the best they are able to do is implement this over ah couple hundred miles at at the maximum.
00:13:42
Speaker
So there's geographic challenges. um If you want to send a message around the world, You have to create a a whole network to try and solve that. it's It's more complicated than just being able to send the information online. So the two fields are very related in that they're both trying to use cryptography to protect our information, just using different resources to do it.
00:14:03
Speaker
And it's post-quantum cryptography that will end up being more widespread because it's going to be implemented on our our classical computers. but like to ask, um what is a cryptographically relevant quantum computer and how close are we to building one?
00:14:15
Speaker
So a cryptographically relevant quantum computer is the fancy term we've came up with for a quantum computer that's big enough to break current levels of cryptography. Right now, companies and and presumably governments around the world are trying to build quantum computers, and we have small ones in existence. ah Companies like IBM and Google have announced machines that hold...
00:14:38
Speaker
30 qubits, 50 qubits, working on up to 100 qubits. When I say a qubit, that means quantum bit, and it's kind of a measure of how large the quantum computer is in some sense.
00:14:49
Speaker
These are are fairly small machines. They can't do a lot in terms of applications yet, but there's progress being made at building them. If we were to look back 5, 10 years ago, now these machines were even smaller back then.
00:15:02
Speaker
So the question is, you know, how long is it going to take until we get one of these computers that's powerful enough to to break RSA, for example? course, nobody knows the answer for certain. That's a ah research question that people are are trying to accelerate as as much as possible.
00:15:17
Speaker
So the best we can do is is estimate. And experts in the field think that there's, you know, maybe 10 years or 15 years is a reasonable chance for when we could have such a quantum computer.
00:15:29
Speaker
All right. What is the timeline for when we might see cryptographically relevant quantum computers? And how should organizations start prepping right now? So, yeah, ah we monitor the progress of quantum computers being built.
00:15:41
Speaker
um The easiest way is just in the media when you see companies like ah IBM or Google or or, you know, others that are building them. Every so often they announce their latest line, that their newest machine and and how many qubits and how much error correction that that it can do. Right now, again, they're still too small. Experts predict that in maybe 10 or 15 years, that is about the time when such a quantum computer ah would exist.
00:16:06
Speaker
But that doesn't mean that we should simply wait until then. There's something known as the harvest now decrypt later threat, which helps us actually understand that ah you can actually be at risk today from one of these future quantum computers, even though it doesn't even yet exist.
00:16:20
Speaker
So think about you're you're a company and you've got a lot of information that, know, whatever field you're in that you want to protect and you need to to keep secret. So you're using cryptography to protect it. You know, it's encrypted. That's what you'd want to do. Maybe you store it in the cloud. Maybe you send it somewhere. You send some of that information somewhere. And maybe an attacker or an adversary is able to get a hold of that encrypted data somehow.
00:16:42
Speaker
Maybe there's ah a hack or a breach or anything. Since it's encrypted, you know, you don't really care because they can't read it. So they they get that information and it's true right now, they can't read it. Cryptography is protecting it.
00:16:54
Speaker
But what if a quantum computer comes out in 10 years and then they can get access to your data? Well, if that information you're protecting needs to be protected for longer than 10 years, you know, you're already in trouble today. They've already got your data and in 10 years, they're going to get access to the information that you don't want to have them.
00:17:11
Speaker
Even though the quantum computer that breaks it isn't even built yet. And so that's one of the motivations why i we're worried about this well in advance of a quantum computer being big enough.
00:17:22
Speaker
um We need to pay attention to this. We need to have
Engineering Challenges in Quantum Computing
00:17:25
Speaker
solutions. It'll take time to find the solutions, to get them standardized, to get them into products. Also, we can defeat that harvest now, decrypt later threat. What are some of the key technical hurdles that researchers must overcome before quantum computers pose a real threat to cryptographic systems? Yeah, so quantum computers are very complicated machines. it's It's the very cutting edge of research and science, and it takes experts in several disciplines coming together together to build these machines.
00:17:54
Speaker
And it's impressive that they have been progressing at the rate that they are. Some of the things that they have to do, first off, some of these machines, they're very, very delicate, and they only can be run in vacuums at temperatures near absolute zero.
00:18:09
Speaker
And when they are putting these quantum... these quantum particles and they're manipulating them and and putting en tangling them and putting them into superposition, they could only get these calculations that they need to do to last for just fractions of a second.
00:18:23
Speaker
And so there's engineering challenges at kind of improving all of those things. Can you make the environment a little easier to work in? Can you entangle the particles so they last for longer than just fractions of a second?
00:18:34
Speaker
Can you work with more and more qubits? Right now, the machines are built so that they can handle roughly 30 to 50 qubits that are put into a chip and they're arranged in certain geometric configurations. They need to scale that so that you can handle thousands of qubits, eventually millions of qubits,
00:18:53
Speaker
and there's some engineering challenges with how you do that so that the particles interact in the way that you want and not in different ways that you don't want. And it turns out as well that when you run some of these algorithms, there are errors that that happen.
00:19:07
Speaker
I mean, that happens in in any computation, but with quantum particles in particular, the errors are significant significant enough that they affect the calculation. So there has to be some error correction done at the end of these calculations.
00:19:20
Speaker
And right now the error rate, it might be around 1% or so, depending on the computer and the algorithm. They need to get the error rate down to much, much lower, like 0.001 or 0.0001, so that i you're able to do more complex um algorithms and computations.
00:19:41
Speaker
So there's a lot that they need to overcome. which for cryptographers, that gives us, you know, time to to work on solutions. But on the other hand, you know, that as I mentioned, there's a lot of ah positive benefits for a quantum computer.
00:19:53
Speaker
we We want those things for society. So there's definitely urgency to build it, even though there's also ah some destructive aspects as well. Absolutely. Now, with some of the challenges that you've had cryptography,
00:20:06
Speaker
cryptography, how do quantum computers break current cryptographic algorithms, particularly those based on factoring large numbers? Yeah, so most of the cryptosystems that we use today, particularly the the public cryptosystems,
00:20:21
Speaker
They use various mathematical techniques and they have kind of certain hard problems or certain trapdoors that they rely on for their security.
00:20:32
Speaker
And the way computers or people try and break them today is they try and ah come up with algorithms to solve that problem. They try and optimize it to find it, how to make that algorithm as efficient as possible.
00:20:44
Speaker
That's what we do with classical computers, and it's the same thing that we will do with quantum computers. So what researchers with quantum computers have been trying to do is design algorithms that will harness the strengths of quantum computers to attack the problems upon which cryptography is based.
00:21:03
Speaker
Now, quantum computers aren't universal machines. They are not going to do absolutely everything faster than our current classical computers. For many problems and situations, classical computers will still be the best tool that we have. They'll be the fastest thing that we have.
00:21:18
Speaker
But for certain quantum algorithms, it's known that they provide ah an an exponential speedup or a polynomial speedup to various problems. So for cryptography, i mentioned that some of the ones that are relevant, there's the factoring problem, and that's what RSA is based on.
00:21:35
Speaker
and There's a quantum algorithm known as Shor's algorithm that is able to to break it. Again, that's based on transforming the factorization problem into a related function for which there is a a period of repetition.
Exploring New Mathematical Problems for PQC
00:21:50
Speaker
And Shor's algorithm ah works to find what that period is. The other cryptosystems that we use today, and these are like elliptic curve cryptography or the Diffie-Hellman problem, they base their security on the discrete log problem.
00:22:03
Speaker
And Schwarz's algorithm, again there, turns out to be able to define the period. You can transform the discrete log to to another related function for which Schwarz's algorithm can can attack it.
00:22:15
Speaker
And so quantum computers, basically, they do just kind of the same as any classical computer is you you look for an algorithm to attack the hard problem that you're based on. And as we keep talking about post-quantum cryptography, we'll see that same sort of cryptanalysis play out and we'll see new areas or new hard problems that we will base cryptosystems on to protect us against quantum computers. Yeah. Now, there's a difference between quantum cryptography and post-quantum cryptography.
00:22:42
Speaker
So what kind of mathematical challenges do post-quantum cryptographic algorithms need to address to defend against quantum computers? Yeah, so that's an interesting area that researchers have been trying to answer for a few decades now, ever since Schor's algorithm was discovered. and researchers have come upon a few different areas of mathematics to come up with new hard problems that are believed to be resistant to attacks from quantum computers.
00:23:08
Speaker
So I can mention a couple of these. One of these is what are called lattices in mathematics. So a lattice is a finite discrete, well it's not finite, it's a discrete set where you take a ah finite number of basis vectors and then you consider all integer linear combinations of these basis vectors.
00:23:29
Speaker
And what that does is it makes us kind of a a geometric pattern, which is, you know, we hear the word lattice, that's what you think of. We we typically think of it in two dimensions or even in three dimensions. But in mathematics, you can define a lattice in dimensions dimensions And there are some problems that you can define using lattices that turns out that nobody knows any good quantum algorithms that can solve.
00:23:53
Speaker
A simple one of these is if I give you, you know, like I create a lattice, I give you the basis vectors that generate that lattice so you can compute with it. What if I pick a random point in the in that space? So we're working in, say, dimension 500, we've got a lattice, and I pick a random point in dimension 500.
00:24:12
Speaker
Well, that lattice is out there. Somewhere there's a lattice point that is close to that point I picked. Can you find me the nearest lattice point to that random point that I picked?
00:24:23
Speaker
Well, it turns out that it is hard for both classical computers and quantum computers, meaning nobody knows any really efficient algorithm to solve that problem. And so that's one example in in the field of lattices where we can use them to define, come up with new cryptosystems for post-quantum cryptography. Without going into all the detail, a few other areas where we have similar problems, we can use what are called error correcting codes to come up with some hard problems.
00:24:49
Speaker
We can use multivariate algebra, which is systems of quadratic equations. And one that's a little bit more closer to the area I research in people have come up with ways to use isogenies of elliptic curves to come up with some post-quantum cryptosystems.
NIST's Role in Post-Quantum Cryptography Standards
00:25:04
Speaker
I'd like to ask you a few questions about NIST's role in post-quantum cryptography development. Could you explain the process in which NIST uses to develop and select algorithms for post-quantum cryptography? Yeah, so let me explain a little bit about NIST and standards and cryptography. So NIST is an agency of the federal government and...
00:25:22
Speaker
The area I'm in, we create what are called cryptographic standards, which is basically a document that says for this particular crypto system, here's how you implement it so that everybody will implement it in the same way.
00:25:34
Speaker
And then, you know, if you are trying to communicate with your bank and send information back and forth, you both need to implement the crypto system in the same way. And because we do this, we're a government agency. Basically, what we do is we create these standards that the federal government uses to protect its information.
00:25:53
Speaker
More widely, these standards get used by industry and other groups around the world. So NIST has a pretty strong reputation for creating strong cryptographic standards that protect our information.
00:26:05
Speaker
We've known at NIST for a while that the public key algorithms that we have standardized are vulnerable to Shor's algorithm. So we knew that we needed to come up with new standards to replace those. First off, we we started assembling a strong team of experts to understand the problem and develop expertise in the different areas of mathematics that are involved in post-quantum cryptography. And then it was back around 2016 that we decided that NIST would do essentially a public competition to select new cryptographic algorithms that we would standardize for post-quantum cryptography.
00:26:40
Speaker
And NIST has done this kind of thing a few times before. where we announce to the cryptographic community, you know, here's a challenge that we need help with. here's here's a We need a new algorithm to do this particular cryptographic capability.
00:26:54
Speaker
And then cryptographers around the world use their expertise. They design solutions, and then they send them in to us at NIST. And our role is... is to manage an open, transparent, and a timely process for evaluation of all these algorithms.
00:27:08
Speaker
So we take the algorithms that are sent in, we post their specifications online, we post their code online, so that anybody around the world can take a look at these and and study them, they can evaluate them, they can implement them, they can try and attack them.
00:27:22
Speaker
And we do the same thing internally at NIST. And so that's what has been going on for the past several years after we kicked off this post-quantum cryptography competition process. um It started in 2016 and we had about 80 algorithms that were submitted into us. And cryptographers quickly got to work.
00:27:41
Speaker
they They enjoy this sort of challenge with all these new algorithms out there. They started trying to ah to attack them. And some of the weaker ones got broken or got attacked. And so what we would do is after a time, we would choose the most promising and move them into the next round of evaluation until ultimately at the end, but we picked the strongest ones for for standardization.
00:28:02
Speaker
So after a period of, i think it is around six years of studying evaluation, we named four algorithms that we would be standardizing as the the new public or the new post-quantum crypto systems that people would then start to use.
00:28:17
Speaker
Now, how does NIFT ensure that PQC algorithms are applicable to all types of devices, including those with with limited computational power, like um Internet of Things devices? Well, we do the best we can, and it turns out the PQC algorithms are are not actually going to work for for absolutely all devices. Researchers have been working on this and they designed the most efficient algorithms that they can.
00:28:40
Speaker
But it turns out that most or pretty much all of the PQC algorithms, the post-quantum crypto algorithms that we use today, they're a little bit bigger than the existing ones like RSA and Diffie-Hellman.
00:28:54
Speaker
They're not too huge. They're not crazy large, but they are bigger than what we use today. So that has some impacts in terms of performance. On the other hand, when you implement them, turns out they're just as efficient, if not ah as efficient in terms of, you know, like the number of clock cycles to implement them or the the number of microseconds that if you were to were to time them.
00:29:14
Speaker
So they will work for the vast, vast majority of our devices, but the very, very smallest ones like Internet of Things. PQC algorithms are probably going to be a little bit too big for them to use.
00:29:26
Speaker
There are other cryptographic algorithms that can be used that are not public key, but they are symmetric key. So it's an active area of research is pushing these things to be as small as they can so that they'll fit on smaller and smaller devices.
00:29:38
Speaker
Why is NIST working on multiple encryption standards and why is it important to have different approaches for encryption and digital signatures? Yeah, so we need to have more than one algorithm available just because we don't want to put all our eggs in one basket.
00:29:51
Speaker
If we choose one algorithm and somebody comes up with an attack and and breaks that algorithm and we don't have any backups, that would be terrible. You know, our information would be vulnerable.
00:30:02
Speaker
So we want to make sure we have different standards that are based on different mathematical assumptions. So if we have a a lattice-based algorithm and someone comes up with a lattice attack, then our backup needs to be based on some other problem, like a code-based crypto system.
00:30:17
Speaker
And so for security, that's that's very, very important. It's also important for performance reasons. I mentioned some of these algorithms are are bigger than what we're used to today. And they they sometimes have different performance profiles. ah For example, there's an algorithm called Classic MacLease that has really, really big public keys, but it's ciphertexts.
00:30:37
Speaker
are very, very small. For some applications, that big public key, it's just not going to work. It's too big. It's a couple megabytes. But for other applications, they they can handle that and they might take advantage of the fact that the ciphertexts are really, really small.
00:30:50
Speaker
So we wanted to as well have different algorithms available for for different applications because they have different performance needs. So yeah, that's that's kind of why we have different approaches. We also have more than one algorithm because we're we're targeting different functionalities. Encryption is what most people think of when we think of cryptography.
00:31:07
Speaker
But there's another important application called digital signatures, which we use for authentication. It's kind of the equivalent of signing your name and somebody can look at your signature and say, yep, you signed that.
00:31:19
Speaker
There's a cryptographic way of doing that as well. And we have to have algorithms to to do that. Now, could you tell us more about the role of lattice and hash functions in the PQC algorithms NIST has selected?
00:31:30
Speaker
and why were these mathematical techniques selected by NIST? Yeah, so of the four algorithms that we selected for standardization back in July of 2022, three of them were based on lattices and the fourth algorithm was based on on hash functions.
00:31:46
Speaker
So the reason that three of them were based on lattices is that over the course of of the process, with experts studying the different algorithms that were submitted, lattices were far and away the most promising area for the algorithms for post-quantum cryptography.
00:32:02
Speaker
They had the smaller key sizes and ciphertext sizes and signature sizes. They were very efficient compared to the other ones. They're faster than codes. They're smaller than codes. And their security has been evaluated more thoroughly than the other areas as well.
00:32:17
Speaker
So the number of research papers, the number of experts that's been involved in this has really advanced the state of cryptanalysis so that we have more confidence in the security of the lattice-based algorithms. So because lattices were so prominent, we ended up with with three lattice-based algorithms.
00:32:33
Speaker
The other... And just for fun, the names of those algorithms, you know, cryptographers choose fun names for these. So we had Crystals Kyber, Crystals Dilithium, at both Star Wars and Star Trek references. We had Falcon.
00:32:45
Speaker
And then the fourth one is Sphinx Plus. And Sphinx Plus is based on hash functions. Hash functions are a cryptographic function that's in our our toolkit. What a hash function does is you can put an arbitrary amount of data into a hash function and it splits it spits out just a small string.
00:33:03
Speaker
typically 256 bits. And cryptographers understand them very well. We know how they work. We can analyze their security. And there is a crypto system designed using them. You know, Sphinx Plus is one example.
00:33:14
Speaker
And so security-wise, we have high confidence in its security. It's widely viewed as one of the most secure of all the algorithms that was submitted. The downside is is that its performance is not as good as in comparison to the lattices. So there's some security performance trade-offs.
00:33:30
Speaker
and it's a little bit bigger and slower and in fact many applications if you force them to use sphinx plus you know they would they would hate you because it's it's just going to be too big for it nonetheless we needed to have some backups that are not based on lattices and we still have a few other algorithms that are being evaluated and will will still be standardized that also don't depend on lattices but these these were the first ones that were selected and that's uh the main reasons why Super interesting with that.
Impact of Quantum Computing on Industries
00:33:57
Speaker
Now, you spoke a little bit about digital signatures before, and it got me thinking about businesses and organizations and how that relates to post-quantum cryptography.
00:34:10
Speaker
Now, how can businesses and organizations prepare to shift these post-quantum cryptographic systems? Yeah, so every business, every organization is using electronic devices. And, you know, we all have digital information that's stored.
00:34:28
Speaker
And whether or not you know it or not, you know, there's cryptography involved in protecting that information. So every business and organization has a potential vulnerability because of the the threat of harvest now decrypt later.
00:34:41
Speaker
And we'll need to transition to these these new algorithms to continue to protect their data. So it's not going to be an easy transition. It's going to be complex. These are new algorithms. They're very, very complicated.
00:34:55
Speaker
They're bigger in some ways, but we know that we we have to do this transition. So what are some of the things that businesses and organizations can do? First, I'd say just education and awareness. You need to know that there's a threat. You need to know that there are new PQC standards that have been developed and published and that you're going to need to transition to these algorithms. Make sure your IT people know this. Make sure your vendors that you're you're buying software applications from, talk to them about PQC and see, are they aware of it? What are they doing to prepare? Are their products going to provide quantum resistance? You also need to find out where you are using cryptography.
00:35:34
Speaker
Where's your data that's being protected? What specific algorithms are being used? So you know where you need to transition from the old algorithms to the new algorithms. And that's not an easy task to do that inventory. um there There are being some tools developed that that could help do that in an automated fashion.
00:35:51
Speaker
But even just saying, OK, download a program, it'll scan your systems, that likely won't uncover everywhere that you're using cryptography. I'd also say, you know, you need to just really devote some resources to this and have somebody who's in charge at your organization of of working on this and that they have the time and and resources allocated so they can help develop a plan for for the particular organization and making sure that this is a priority in the coming years.
00:36:17
Speaker
This transition is not going to be done in just six months or a year. it It'll take ah a number of years. While quantum computers pose a threat to cybersecurity, what are some of the potential societal and commercial benefits they could bring?
00:36:30
Speaker
Yeah. So we've been talking about the the dark side, the fact that they're going to attack or break some crypto systems. But that's not the reason that Google and IBM are are trying to build these things.
00:36:40
Speaker
There's going to be some economic reasons why they want to do that. For example, some of the things it's known that quantum computers will be able to do is better optimization. This will improve logistics challenges, be able to solve, you know, when you have a huge number of variables that you're trying to solve a system with and design the most efficient way of doing something, having a quantum computer that provides an exponential speed up, that will be be one area.
00:37:05
Speaker
It will improve the state of the art in chemical simulation. So scientists spend a lot of time trying to look at molecules and design new molecules and study their properties and see how those can be used to to do various things, design drugs and so forth.
00:37:22
Speaker
Quantum computers, this is one of the areas where it's known they will provide a speed up compared to what classical computers can do today. Another one is combining the power of quantum with another area that people are very interested in, and that's machine learning.
00:37:36
Speaker
what We're able to harvest a lot of data right now by doing machine learning and use artificial intelligence to define insights and patterns and solve problems. When we're able to combine that with quantum computing, it's known very much that this will be way more powerful than what classical computers can do on their own.
00:37:54
Speaker
So all the benefits of machine learning will be just taken to a new level with quantum computers. How can policymakers strike a balance between managing the cybersecurity risks posed by quantum computing and realizing its potential benefits?
00:38:06
Speaker
Yeah, so policymakers and the government, they they do want to encourage the quantum computers to be built and developed because of the scientific reasons for that, the economic reasons. There's financial systems that would would benefit from this.
00:38:21
Speaker
So they want to encourage that. They want investment in quantum technologies um because it will do ah do a lot of good.
Balancing Quantum Development with Security
00:38:26
Speaker
the risk of them breaking computers is known. But because we have been preparing new algorithms and new standards, that's kind of been the balance that we're doing. We're not trying to slow down quantum computing in any way.
00:38:37
Speaker
We're trying to just speed up the process of making sure that we have standards and that people can transition to these new algorithms. So some examples of ways that the government has done that, the U.S. government put out some national security memos. Congress passed a law directing all federal agencies to be aware of the threat.
00:38:53
Speaker
And the main goal of the United States government is that we want to transition to these new crypto systems by the year 2035. which which sounds far off. It sounds like we have plenty of time.
00:39:04
Speaker
But from experience, we know that not everyone will be able to finish by that time, um even though it's 11 years in the future. So by putting a date out there, though, and making sure people know that this is the goal, that that encourages a lot of people to begin the transition and work to towards becoming quantum protected. We know that everything, whether it's been from folks learning about a new technology to the U.S. or any sort of system converting to electric vehicles, there's always going to be challenges.
00:39:32
Speaker
Now, with that, what do you really want listeners to take away from this research and this topic? First off, hopefully you find this very, very interesting. Cryptography, quantum computers.
00:39:43
Speaker
For the average person, this is all going to be taken care of behind the scenes if everything goes, you know, as as good as we hope. There's a threat from quantum computers that they will be able to attack the crypto systems that we rely on today to protect our information.
00:39:58
Speaker
They are a powerful threat. Foreign adversaries, it's already known, are are collecting our data with the goal of being able to decrypt it into the future. Fortunately, you know, we at NIST have been on top of this and we have been making sure that we will have solutions ready that can protect us.
00:40:13
Speaker
So just earlier this summer, in August of 2024, published these first... um PQC standards so that people have algorithms that they can use to protect their information.
00:40:24
Speaker
So hopefully, you know, the people that are needing to transition these algorithms, companies and organizations, they are aware of the threat and hopefully they're aware that there are solutions and that they will need to migrate to these solutions. And for everyone else, you know, mathematics is a fun area of exploration and research and the applications in cryptography are very, very important.
00:40:46
Speaker
And we need more people to to go into this field because this will certainly be continued to be studied in the future. Thank you for coming on Breaking Math. And we had a great time.