Transcription
You may not love hard math problems because, well, they're hard. Or maybe you enjoy suffering. Don't worry, I'm not judging. But you do benefit from the fact that hard math problems exist, whether you know it or not. In fact, we all do. These are the basis for modern cryptography, which is how we keep our secrets secret. Things like personally identifiable information, personal health information, intellectual property, business records. This kind of information is stuff that we need to keep secret. Without this capability, the internet as we know it would cease to exist. There would be no way to know you are really you, and no way keep your personal information from becoming public.
So what do I mean by hard math problems? Let's start with a few examples. We'll start with something easy. First, if I ask you to add these two numbers, I think you can do that. That one's an easy math problem. If we base our crypto on something like that, we're not gonna have much of a secret. But let's try something a little harder. Let's say I want you to pick two prime numbers that multiplied together will equal this number, 21. Now, what's a prime number? It's a number that's evenly divisible only by that number and one. So, that, the prime number, you can think of two numbers multiplied together will give you 21. Again, not really hard. Seven and three give you 21, and both of those are prime numbers. So, not so terribly hard. But then, what if I asked you the same problem where we've got P1 and P2, the two prime numbers, and I want you to find the two prime factors of a 600-digit number? Okay, now your mind is blown. In fact, the same would be true of the best supercomputers we have today. It would take them thousands of years possibly in order to solve that. But a sufficiently strong quantum computer could solve that in just a matter of hours. And since this is the hard math problem, that's the basis for some of our best classical cryptography, things like the RSA algorithm, which we use every day, whether you know it or not. Then, if we had a quantum system that could break that easily, then that means that crypto would break easily. And all of a sudden, all the secrecy that we need would evaporate.
So what's the solution? It's a thing called lattice cryptography, and it's based on hard math problems that are massively more difficult than finding prime factors of large numbers. Let's take a look at the high-level concepts behind this type of quantum-safe crypto to get a better understanding. But don't worry, this is the end of the math. We're not gonna do a lot of deep dive on that. I'll try to keep that to a minimum. But, I'm gonna ask you, don't give me a hard time if I don't get all the precise details because that will make for a really long and really boring video. So, you ready? Let's go.
Okay, how about a game of chess? Well, not a full game of chess, but let's use this as an analogy to figure out how lattice cryptography works. So we'll start with a really simple example. You've got a knight, and you know in chess a knight can basically move over one and up two, or it can go over two and up one. And that way it could reach a spot right here with some combination of moves. Now, imagine though, that's an easy thing to do if I told you I want you to hit that particular spot. What if I tell you, I want to hit this particular spot, which is not exactly in the center of one of these. So you can't hit it exactly. Now you're gonna have to do the best possible approximation you can to get to it. Well, you could go over two and up one, and then you could over two more and up one, and you miss it just a little bit. Or you could, again, go over two and up one, and you could go up one and over two, and again you slightly miss it. So, you could try a number of different combinations. You could go all the way around the board and work your way back around to get a little bit closer. But you can see there's a lot of different combinations that would get you into that. What I've done is created some complexity into the problem. Not complexity you'd have in a real chess game, but this is an illustration. So, we took what was a two plus one or a one plus two, which was our way of describing how the moves would happen on the board. And if I wanted to make it even more complex, I'd turn that into an x plus y. So now it's a variable number of moves that could happen. That's one way to increase the complexity. It's not chess anymore, but you can see how it gets more complex. What if I take this, this was two-dimensional, so you could kind of spot that because we can see in two dimensions pretty easily. And what if I turn that into a thousand dimensions? Now that's a really hard problem to deal with. And then, what if add noise into the equation? And noise is basically this, where I'm putting it, where it's not a space that you can actually land on. You're gonna have to get as close as you can without actually hitting it. And this noise, along with multiple dimensions, along with other variables, it's what takes what looks like a very simple problem and turns it into a very hard math problem, something where we do learning with errors. And that is the basis of lattice crypto.
Okay, now let's go over to lattices. We've looked at one simple analysis, but let's do something more complicated. So we're gonna take these complexity rules and park those over here, but we're going to refer back to those. So, what is a lattice? Well, a lattice is something that you create in multidimensional space, and it starts with an origin point. And then from that origin point, we have a couple of vectors, basis vectors. So I'm gonna have one vector here, a green one that goes about 45-degree angle. I'm going to have a blue one that goes horizontal completely and it's about twice as long as the green. So those are two different vectors. And basically any combination of those vectors create a point in space. And that point in space is another part of the lattice. So if we construct the lattice, it's basically every possible combination of those two vectors. So to give you an idea of what I mean. So I've created, if I do one green vector, then that's going to create that point in space. If I do 1 blue vector, it is going to create this point in space. Now, what if I do some combinations? What if I do two green vectors? Well, that'll get me here. If I do one green and one blue, then that's going to get me over to here. So, you can see I can keep constructing this over and over and over again. And ultimately, I'll create this lattice space. Now, here's the hard problem. So now what I've taken is what was a simple 2 plus 1 and now made it a more complex problem by adding x plus y. You could have any combination of these things that you're adding up. The other thing I'm going to do is introduce the noise. So, the noise is going to say, here is the spot I want you to reach. How are you gonna reach that? Well, there's a lot of different ways you could approximate it. You could continue adding greens until you get close and each one of those will create spots in space. I could add a couple of greens plus a blue and that gets me maybe a little, little bit closer. Maybe I'm gonna add a coupla greens plus a blue plus another green and that gets me maybe even a little bit closer still. You can see I've got to do a number of different trial-and-error possibilities. There might even be some others that, that you can eyeball and see we could try and would get us close to that spot. But the fact that this doesn't fall exactly in the lattice space as one of those points is what's the noise that's making it a little more difficult. You say, okay, it still doesn't look all that hard. Well, that's because you're looking at it with only two vectors and you're only looking at two dimensions. Let's make it not one dimension or not two dimensions but let's make it a thousand dimensions. Once I do that, now, your mind is blown. And not only is your mind blown in trying to figure out that, you're going to have to try what will seem to you an infinite number of possibilities. Also, so would the mind of our best supercomputers today be blown. They wouldn't be able to solve this either. Because what we're looking for with a good cryptography algorithm is to make sure that there's no way to get to the end game, no way, to solve the problem through some sort of shortcut. It needs to be something that requires brute force, trying one possibility, another, another, another, and you just keep having to try too many possibilities. And it takes a thousand years or more for you to finally try all those possibilities. So, that's another thing. And then, if you can't solve it and a supercomputer can't solving it, the real question is, can a quantum computer solve it? And the answer is no. A quantum computer sufficiently strong that can break all of our existing crypto still can't solve this problem if you make the lattice complex enough and introduce enough noise. So that's the basis then for our cryptography that is going to survive the quantum menace.
Okay, the good news is you don't have to figure all this stuff out. The smart cryptographers have done all that hard work for us, and they've come up with a set of what are known as quantum-safe crypto algorithms, or sometimes they're also called post-quantum cryptography. And they basically embody this kind of lattice arithmetic and this hard math problem. The U.S. National Institute of Standards and Technology started a call for proposals about 10 years ago where they were asking for new algorithms that quantum computers wouldn't be able to break, and the best minds came together and started coalescing around these, these lattice crypto algorithms. So the good news is those exist and you can use them today. They're actually out on open-source repositories. They're industry standards and you can start deploying. So, that's the good news. And Q Day is coming when our quantum systems will be able to break our existing crypto. So you need to start on this now.
Now, what should you be doing? Now that we have a solution, what should you be doing to actually implement that? Well, it starts with discovery. I need to know about all the uses of cryptography in my environment. If I don't know, I can't fix them, of course. And out of that discovery, I'm gonna create a thing we call a crypto bill of materials, a C-bomb. That's our basic inventory of all of our uses of cryptography in our environment. From there, I am gonna need to evaluate all of those and I'm going to need to decide in which cases do we have weak cryptography that a quantum system would be able to break, and what do we need to do to fix those. Then I'm going to prioritize these things because I need to make sure that I'm ... I'm not going to be able fix all of these in one day. The reality is a lot of organizations have hundreds if not thousands of instances of custom crypto that they're going to need to repair. So, I want to go after the most sensitive ones first and build a plan and manage that conversion. Then I'm gonna finally do the remediation. This is where I'm going to try to figure out what kinds of things do I need to change. Do I need to change key links in some cases? Do I need to go with new algorithms entirely? That's what we're gonna do. And ultimately, keep repeating this process. Go back, this is not a one-time thing. And with the ultimate goal, what we're trying to get here is this notion of crypto agility. I want to make sure that in the future, if we find one of the algorithms that we selected in fact has a weakness, I don't want to go back through all this process again. I want it to go right to my C-bomb and say that algorithm is messed up. We need to swap it out with another, and we'll be able to do that in fairly short order if we've done this process correctly. So, that's our ultimate goal, is crypto agility and move toward quantum-safe cryptography.
Sometimes, difficult actually means good. The harder the math problem, the stronger the crypto—because it forces an attacker to result to a brute force attack of all possible combinations. And that's a win for the good guys, because there are too many guesses for even a quantum computer to try. That means our secrets stay secret, which is what we want. Oh, and the good news is, you don't need a quantum computer in order to do quantum-safe crypto. It runs these algorithms on our systems today. So you don't have to go buy one of these in order to ensure that your secrets will stay secret. But here's the lesson you don't want to miss: you need to start now on your path to post-quantum crypto because of this, these four letters: harvest now, decrypt later. What that means is, if I make a copy of your encrypted data today, then in the future, I'll just wait until a sufficiently strong quantum system comes along, and I'll be able to decrypt it at that point. Or, if I copied your data last year or 10 years ago, I'll eventually have access to a quantum system that will be able to decrypt it later. So, we need to start securing the data now, unless, of course, you have a time machine and you can just go back in time and re-encrypt all your data in the past. But if you do that option, make sure you come back to the present because we're going to miss you.