Post-Quantum 101: What is Post-Quantum Cryptography?

Welcome to a special episode of Cloudflare TV. You're watching PostQuantum 101. What is PostQuantum Cryptography? My name is Jason Kincaid. I'm super excited to have Sofía Celi here from Cloudflare's research team. Sofía, could you please introduce yourself? Yes. Hi, Jason. Hi, everyone. Thank you so much for having me. My name is Sofía Celi, and I'm from Cloudflare's research team. Nowadays, I do mostly PostQuantum Cryptography and its applications. So, happy to be here. Awesome. What does Cloudflare research do in general? What Cloudflare research does is a lot of research, but not mostly theoretical research, but rather research that has an applicability to the real world, to our real connections that we have, and it has an actual impact into the Internet nowadays. So, there's many projects that we have. Some of them are about preserving certain privacy properties. Some of them are about understanding more how certain capabilities of the Internet are used by using metrics. Other ones are by trying to integrate PostQuantum Cryptography into our connections. Awesome. Which brings us to today and this session. So, why don't we start off by talking a little bit about what are quantum computers? Yeah. It's a term that may inspire some degree of, well, they can be a little mind-bending, but let's take it from a high level. Yes. So, generally, when one uses in the everyday life, the computers that we use follow more like a classical mechanics way of viewing, which one state is either one thing or the other. So, you have one or zero, you have a bit that is either on or off. And during long time ago, what many physicists, including Richard Feynman and Yuri Mani, realized is that while these computers are great for everyday needs, they don't seem to be so feasible to be used to simulate quantum mechanics experiments. The reason being not that classical computers cannot, but they will need so much time and so much memory and so many resources that it will be infeasible to try to execute this experiment. So, they came with this idea of a quantum computer, which contrary to what a classical computer is, which follows more the properties of classical mechanics, what a quantum computer is, is that it follows the properties from quantum mechanics. So, instead of having a bit that is either one thing or another, you have a qubit, which is basically a superposition of different states until you collapse it into one. Awesome. So, I'm going to touch briefly on some analogies here, because this is a realm that, as I mentioned before, is a little bit mind -bending, and I tend to find analogies can be helpful. And there are a lot of analogies out there around quantum computing. So, Sophia mentioned superposition. So, a good analogy I've seen is you've got a coin, and it can be head or tails, and you can have, what superposition is, it's sort of like the coin is spinning. So, it's both heads and tails, and there's like a probability involved of what it's going to land on. And another analogy I'll use, and something you'll find if you try researching various analogies, is that many experts will say that they are wrong and misleading for all sorts of ways. So, I will use one analogy that's just kind of distilling things down, because ultimately what's important is that you understand why this matters. And here's my very basic completely misleading analogy, is imagine you are in the Star Wars universe, and you get into your spaceship, and you're taking off from the planet, right? And maybe you get hailed by a friend that's in another city on the same planet. You're using your conventional starship engine, right? And it's fast enough to get you around the planet, and maybe to like a nearby moon, but if you're trying to get across the galaxy, you're going to use the hyperdrive, right? You've got to punch in the coordinates, it's going to do a bunch of calculations, and whoo, you're working through space, and you're using a different kind of physics. And so, that is the analogy I'd use to compare conventional computers to quantum computers, which is to say the conventional computers, they are the standard engine, they're flexible, right? They get you where you need to go in many cases, but when you're trying to traverse really long distances, well, that's when you're shifting gears, and you're traveling through hyperspace, and that's kind of what the quantum computer is like, right? What do you say, Sofia? Is that roughly in a ballpark that sort of is... Yes, I think the important thing always with quantum computers is more than understanding that they don't solve impossible problems, but what they do is that they solve certain problems that in classical computers are very difficult in the sense that it takes too much time to try to solve them. What quantum computers do is that they solve them in a really efficient time, and that's like their real power. It's not that they solve something that is unsolvable, it's just that they solve what usually takes a lot of time in a classical computer, they solve it really, really fast. Yeah, and the analogy like a classical computer will get you anywhere, but it will take you like millions of years to arrive there. With a quantum computer, it won't. Exactly, exactly, and really what's important for those of you who are just kind of getting up to speed with this stuff is the implications of that. It's not so much... It's great if you understand how quantum computers work, but you don't necessarily need to, and if you want to dig further into how quantum computers work, there's a link under this video in the description. Check out the comic strip called The Talk, which gets into it and talks about some of the analogies and how they're useful and sometimes not so useful, but with that said, why don't we talk a little bit about why this matters? So the first thing is, why are quantum computers good for the world? Why are people working on these? Yeah, so there's several problems that quantum computers solve in much faster time, and that's why they make them great. So the first thing is what was mentioned earlier, which is that they can actually simulate certain quantum mechanics phenomena that will be really difficult to simulate with classical computers, which means that we have a better understanding of the universe with them. The second thing is that because they, for example, one of the problems that they solve in an efficient time is the problem of searching. So sometimes in computers, what you use for solving the searching problem is that you go, you have an array, and you go by each element of the array until you find the correct one, which means that in the worst case, if your element is at the end of the array, you will have to go for the end length of this array. There are other algorithms in classical computers that make this problem a little bit more efficient, but not so efficient. With quantum computers, on the contrary, you can find really, really fast the correct element that you are searching for, which means that in certain problems and certain new mechanisms to try to solve certain diseases, this can help to either create better targeted medicines. So they bring like all of these new ideas in which, yeah, in which it makes science for the better by the way that they are using in this much faster way, the algorithm. So the conventional computers, we can try to make these rough approximations of molecules and how they behave in a living organism. With a quantum computer, we have the potential to really make it a much more accurate and then potentially a much more effective therapeutic potentially much more quickly. And so that's where, and that's just one use case that we've, that various researchers have thought of. And so there's a lot of opportunity there. Now that said, why, why is this something that, you know, there's, there's reason for us to not necessarily be worried, but we want to make sure that we're being thoughtful about the development of quantum computers. And I know this, this involves cryptography. So why don't we talk a little bit about that? Yeah. So here, maybe first to start with was how cryptography gets built. So in general, in cryptography, you try to create an algorithm that it has a base that is a mathematical problem that is hard to solve. So most of the time, what we use in our connections is cryptography that is based on the factorization problem, for example, that is easy for us to take a number and just exponentiate it to another number and get a result, which is going to be a public key, but it's difficult to do the inverse operation in an efficient time. So if I give you an X number, a really gigantic prime number, it's really difficult to understand what's, what resulted into that number, which two numbers resulted into this number. And that is really difficult also, not only for us humans to try to solve, but also for a, for a classical computer to solve. Most of the algorithms are really inefficient. It doesn't mean that it's impossible, but it means that it will take a computer really long time to solve this problem. And that's why we use it nowadays in our connections, because we think that adversities are not going to be running with 500 computers for like 2000 years until they solve one instance of this problem. So we say, okay, this is not perfectly secure, but it seems that an adversity will not want, will not want to actually having computers run for thousands of years until they solve one problem. The problem is that with quantum computers, this problem becomes really easy to solve. And the specific one that I'm talking, which is the factorization problem, there's an algorithm that is called Shor's algorithm that indeed makes this problem much more simple to solve. In consequence, what this means is that most of the connections that we use nowadays get broken with a quantum computer. And what it is a little bit worrisome is that it's not something that only happens for the future, meaning when a quantum computer comes, but rather that it could be happening as of today, because certain adversities could be recording traffic right now, for example, storing all the traffic that happens, that is moving through the Internet in a server encrypted. And then when quantum computers arrive, they will be able not to decrypt, not only to decrypt future traffic, but also anything that was stored in the past. So that's the worrisome thing, that they break most of the cryptography use today. Not all cryptography, because Hash's symmetric algorithm seems to be safe against the potential of quantum computers. Super interesting. Let me say that back to you to make sure I understood it. So basically, the way our current encryption approaches work is that they use complicated math that conventional computers find very challenging. And that a conventional computer could eventually solve this math problem, but it would take longer than any of us or any of our descendants is likely to be alive. And whereas with quantum computers, it turns that math problem into something that can be solved just like that. And so that means you can potentially break encryption. And whereas quantum computers, to our knowledge, aren't in operation right now, that this data may be kind of being stored somewhere. And that once this technology, the quantum computers are invented, they could potentially be applied on that data, which adds urgency to this. It sounds like it's quite important that we figure out a way to secure data in such a way that even if we're confident that these computers don't yet exist, that no one is subsequently going to be able to examine that data. So let's say if these connections or these encryptions do get broken, how do we protect our data now? Yeah, so there's now actually certain new mathematical problems that we can use. It's not that they started right now, these mathematical problems, they existed for a really long time, but now they have arrived to being more publicly known because quantum computers seem to becoming a reality. So for the last years, the National Institute of Technology has been running a process of standardization, certain algorithms. And the purpose of this process is to come up with a recommendation of algorithms whose mathematical base is safe against quantum computers. And we know already some of those problems. So one can use certain problems on lattices, for example, or one can use certain problems on isogenies, or one can use cryptography that is based on certain problems that we know that are not broken by quantum computers. So for example, hashes are not broken by quantum computers, so we can still use that. So basically, we do have a path to go forward. And right now, as part of this process, what is happening is that a lot of experts came together and proposed new algorithms. And the community is also analyzing that the security properties are what they are supposed to be, and that the implementation of these algorithms are secure, and that they also fit into our everyday connections, and that they fit our needs of an ever-faster Internet. Got it. So let's pause for a second, talk a little bit about, I am not going to pretend that lattices are in my wheelhouse, but I do think we can talk a little bit about what these entail. What is a lattice? So basically, a lattice is, yeah, maybe I can actually show, a lattice is that. And this is a structure that was built in Portugal to prevent houses from being destroyed during earthquakes, specifically in Lisbon. So that's basically a lattice. So lattices are basically these repeated and periodic arrangements or points, periodic arrangements of points in a specific space. And while that is really nice, the problem that we'd rather try to use to create a post-quantum algorithm is, for example, the problem of learning with errors on lattices. So the bounded distance decoding problem on lattices. So on the first one, so for example, on the learning with errors, if we think of this problem from a lattice perspective, what you basically have is that you have these repeated arrangements of points on the state. So in our case, for example, there, the points will be this, sorry, this one over here. This is a point. Okay. Sorry. This one is a point. Okay. So those will be the points into the lattices. So what's the learning with errors is that you've given to someone else a point, let's say this one, but you had a small error to it. So you add some error and you just point there the point to be here. So it's not anymore a point on the lattice, but it's something that was generated from a point on the lattice. And eventually you ask the problem ask, what is the closest point to that error at the point? And you know that it is here because it's really easy to, for us to see, because we are basically using a three-dimensional space and we can see it kind of a three-dimensional space. In reality, we're using kind of a two -dimensional space with that arrangement. And that's really easy to see in that kind of dimensions. But if you give an amount of dimensions as you give in lattices problems, trying to figure out what is the closest point to this error added point is really difficult. So that's, for example, something that is difficult to sign, even for a quantum computer. Got it. Again, let me try saying that back to make sure I got it. So right now, if you use Google Maps or something, the computer is really good at finding the distance from A to B. It'll calculate that. But if we made a map in 300 dimensions, then the computer would really struggle to find the distance, or at least the shortest distance from A to B. If you said, what is it? Because there's so many different, I don't know what 300 dimensions look like. And it sounds like computers have a hard time with it too. But the math is, you can make a math equation that describes 300 dimensions, as I understand it. Yes. And that is sort of the crux of at least one of these approaches to post-quantum cryptography, is that even a quantum computer would struggle with that kind of math problem. Yeah. Yeah, that's a security assumption that you have in the lattice space algorithms, that you're basically saying that this problem is as hard as the learning with errors problem. And on top of that, you take that mathematical problem, that assumption, and then you build your functions and your algorithms out of it, and you would have the algorithm that you can integrate into your protocols. So how do we figure out what problems the quantum computers are bad at? Is there like a certain, because it sounds like lattices, I'm curious, sort of like, how did we land on like, it happens the quantum computers are bad at this one, but they're good at these other problems. Like, how are we exploring and researching that? Yes. So that's a really intriguing question. Because for the first thing, it happens that it happens on every classical computer. Right now, for example, we cannot solve very efficiently the factorization problem, the inverse of exponentiation, because we don't know of an algorithm that solves this in efficient time. But it doesn't mean that it doesn't exist. Maybe it exists. Maybe there's some undergrad or some mathematician somewhere that manages to solve it. And then we don't even need a quantum computer, because this person came up with this algorithm with this fancy math and actually solve it. We just have right now, because it has passed so many years, and no one has solved this problem in efficient time, we have the assurance that indeed it's not possible to break at least right now, because no one has broken it yet. The same with quantum computers. Right now, there's no quantum algorithms that solve this problem in a really efficient time, and therefore we can deem them safe. But it doesn't mean that sometime in the future, maybe in like, I don't know, 2,000 years, someone will come with a way to actually break these algorithms as well. Because as I was saying, cryptography is not perfect. In every case, it's perfect with probabilities. So we have the probability that we know that these algorithms are safe against quantum adversity, because no one yet has found a way to do this efficiently, even with a quantum computer, with a classical computer. But it doesn't mean that it's like 100% perfect, no one will ever break it at all. No, cryptography is more about probabilities of break. And how are we testing? Because we, I know we, well, here's a good question. I have seen various companies talk about, you know, we now have a quantum computer, and yet it seems like people, you know, they're concerned about the possibility of eventually stored data being essentially having their cryptography broken by quantum computers. But the ones that exist, the quantum computers that do exist, it seems like we're not too concerned about that. So can you talk a little bit about what is the current state of the quantum computers? Yeah, so quantum computers have made an enormous advances compared to other decades lately, specifically in the problem that we hear about in cryptography, which is the factorization one. Recently, some years ago, actually not so recently, a quantum computer was able to factor the number 15, which we know that's three times five. And it's really, really easy for us to see. And yeah, you learn that in like high school, actually, no, in elementary school, you learn about that. So it's really easy. And just to jump in, that's the kind of problem that sort of is the foundation of modern cryptography, right? It's not three times five, but it's a big number. And what are the factors of it, right? Yes. Yeah, it's actually five plus five times five, sorry, don't use that one. But it's actually using really, really large prime numbers. But right now, a computer was able to factor the number 15, which basically means that they are stable enough, a quantum computer is stable enough to actually find the correct answer in this array of superposition that exists. And this is really, really good. Those are like the latest advances. And then what this means is that, again, we are starting to have this stress to cryptography, because if this problem now is stable enough, then all the numbers are going to be started to also be checked, and you increase them and increase them until you actually arrive to a point in which by which we're using numbers that we use in our everyday connections. Something that is really interesting to talk about as well is that it's really difficult to actually say when a quantum computer has actually surpassed a classical computer. There's some terminology on actually define this as quantum supremacy, which basically is the idea that now a quantum computer is able to solve this specific problem in a much more efficient time than a classical computer. And that seems great. And some people have said that indeed, we have arrived to quantum supremacy because we were able to factor certain numbers. But at the same time, it's difficult to actually say that this is 100% absolute truth, because it could mean that maybe a classical computer in the future will also be able to arrive to the solution of factorization problems, because I don't know, some mathematician found a way to do it more quickly. Or it turns out that now we can store memory in the computers in such a way that it's really easy to do, or like the times that this operation takes the computer becomes so fast in classical computers that then it's also possible. So this idea of quantum supremacy and actually how we determine is still a little bit difficult to define. Got it. Got it. So it sounds like we still have a little bit of time to get this sorted. So now we've talked a little bit about sort of the existence of the quantum algorithms, or I should say the post-quantum algorithms. Do these solve our problems or are there remaining challenges and what are those and how are we going to potentially address them? Yeah. So the first thing, the first challenge that actually is still somehow debated is that if someone will come up with a quantum algorithm which will also break these new mathematical problems, that could be a possibility. It doesn't seem sophisticable, but it could be a possibility. So the security of the algorithms also has to be properly defined in those terms. The second is if indeed all of these post-quantum algorithms fit into our everyday connections needs. So there's a way actually to solve the quantum problem of quantum computers breaking algorithms. If we increase the numbers to, for example, terabytes of keys, then of course a quantum computer will also have a harder time of actually finding a solution. But increasing the numbers of our keys for everyday connections is kind of not great because it will be that our connections are really slow, that our connections will time out, that every time that you want to open a website it will take you like 10 minutes of that website to load, that no one would actually be using the Internet as it is nowadays. So one of the big challenges is that, is how do we fit these new post -quantum algorithms in the Internet that we have nowadays that is so, that loves so much the fast connections, that once every instant leave, will it actually make it change? Because all of the post-quantum algorithms right now proposed as part of the NIST post-quantum process have bigger sizes or have computation times that are bigger than classical cryptography, which means that maybe we will see a little bit slower of connections. Will this be actually an impact to the user is also something that is still a question in the sense of like, there's still much research needed from the UX perspective for actually understanding how slow is too slow for a user to open a website and like, wait like five minutes. Is that too slow? Will users be comfortable with that? That's still the question. So that's all the, a little bit of the open challenges in post-quantum cryptography. Got it. So even though we've got some algorithms that we believe are hardened against quantum computers, it's the matter of like, how do we implement these in a way such that the Internet in general and like various, each web request and so on includes essentially these larger packet or payloads and it might kind of bog down connections. And it reminds me, back in the days before all websites using SSL, there was this sort of association between, oh, it was going to slow down each website. So people were sort of wary of doing it. And then what, do we expect something to change here the way that it did back then? Yes. So in TLS, there was also a big push for adding cryptography that was faster. So one of the big wins of the cryptography that we use nowadays, which is elliptical cryptography, is that it's really fast to use in everyday connections. So that was everybody basically because it's really, really fast. And there was a big push from the community to actually make the operations that these algorithms use very fast and to make the storage needed, the hardware needed for these algorithms also very fast. The same path could go for post -quantum cryptography or to try to optimize the operation of these algorithms as much as possible. There's a big effort on that. But the keys, for example, they remain the same. They remain very, very long. So for example, on the first connections that we use, that we do in TLS, we will have to be transmitting those keys, those really long keys somehow. And that still needs some thoughts of like, if it properly is going to work on every part of the world, even in the parts of the world that don't have the fastest Internet, we also don't want them to just lose connections because now we have post -quantum cryptography. So if that indeed works. On the other Cloudflare, we have been doing a lot of experimentation around the matter, specifically on TLS, to see if indeed all of these algorithms fit in a TLS handshake and how does it look. So far it's looking good, at least for the confidentiality part. For the authentication, it seems that we need a little bit more work. And related to the work that Cloudflare and the research team have been doing, I know last week we had a great series of blog posts, and make sure you're tuning in to Cloudflare TV the rest of this week, because we've got some more great segments coming up. Do you want to talk a little bit about the work that you wrote about last week and what Cloudflare is doing in this? Yes. So last week we wrote a lot of blog posts that not only are about showing the experiments that we are currently doing, but also trying to make the community understand what is quantum computers, what is quantum cryptography, what are the flavorings, what are the challenges of it. And also finally announcing that we are migrating all of our connections, internal connections, to post-quantum cryptography, because we do believe in helping build a better Internet. And this also means preventing quantum adversities or classical adversities right now, recording encrypted traffic and then coming up with a quantum computer and being able to decrypt that traffic. So we want to prevent that. So that's why we are post -quantumifying our connections. Not only adding post-quantum cryptography, because if we add post-quantum cryptography only and it turns out in like, I don't know, 300 years that it's broken, it's not the best thing. We add it in a hybrid way, meaning we add a classical algorithm and also post-quantum one. Got it. So that's very exciting. And that's, it's sort of, it's almost just the beginning, right? Because while we're securing the internal traffic, do we have plans to sort of bring this externally and how is that going to go? We've only got about a minute left, but I want to make sure we talk briefly about that. Yes. Our idea is also to eventually bring it externally in the processes that we can. So for example, one of the announcements was as well that the work client could be indeed post -quantumfied. And that's a client that indeed even lives at the client side, at the end of the client side. There's other ones that we cannot, we cannot change until the client device, for example, we right now don't have a browser that we can change, but we know that other browsers are trying to be interested also migrating to post-quantum cryptography. So you're using Cloudflare with a browser that has this migration, then you have a full post -quantum path. Awesome. Well, again, you know, this stuff sounds even for folks like me who don't understand the realm of quantum super well, it's clear that this really matters and it's important that Cloudflare keep working on it and standards get adopted so that we can be protecting these connections. We've only got a few seconds left. Sophia, I want to say thank you so much for walking us through this. Super fascinating. Really appreciate it. And everyone don't miss the blog posts that are linked below. Yes. Thank you very much. I'm really happy to hear.