Post Quantum Cryptography - Computerphile

Key Takeaways

It's time to panic, Shawn. We need to implement post-quantum. Post-quantum? Post-quantum algorithms. All right, we should all panic, all right? >> This has nothing to do with the mailbox. This is We shouldn't panic. We could talk about post-quantum today, right? Post-quantum is algorithms that are robust to quantum attack, all right? So, we have a bunch of cryptography that that underpins most of what we do, for example, online or on any computer system, really. And a lot of this is quite vulnerable to specific attacks if a quantum computer was invented that was big enough, all right? And such a computer doesn't exist today, but we can't rule out that it wouldn't in the future. And so, the question is, when do we panic and how much do we panic? As of recording this video, there's lots of companies working on quantum computers, right? We've done some videos on quantum before. The biggest quantum computers are somewhere around 50 cubits, all right? Like And this is error-corrected cubits. So, it could cubits that have some resistance to to be sort of noise of the system. Um Shor's algorithm, right, which is um the algorithm that factors large integers and can solve discrete logarithms as well, right? Kind of like the the gold standard for algorithms on a quantum computer. To break an RSA key would need somewhere around 4,000 cubits, all right? So, it's safe to say we are not there, all right? There's a question as to whether we will ever be there, all right? Or if we are going to be, what the time scale is, right? Conservatively, the Well, no, actually, even ambitiously, the time scale is in the order of decades, I think, right? But, you know, we may be here in 30 years with me very gray explaining to you, and you've got a bit old, so you're shaking the camera around. Even more. >> Yeah. And say, you know, we're still 30 years off this quantum thing. What a waste of time that was, right? I don't know. That's what's so what's so interesting about it. So, post-quantum is not about, "Oh, no, there's a there's a quantum computer." It's, there's a small chance of a quantum computer. Can we make some informed decisions about this? There are two quantum algorithms that we could just briefly mention, right? There's Grover's algorithm. And Grover's algorithm takes a search problem and square roots the run time. Suppose you're trying to break an AES key. And your AES key is 128-bits. Now, on a classical computer, you would do two to the 128 operations to brute force that. You would guess a key, does it work? No. Guess a key, does it work? No. All right, and you just keep going. This is very, very slow. Grover's square roots this, right? So, the actual search space will be two to the 64. Now, two to the 64 is kind of within reach, right? So, that's getting a little bit uncomfortable if such a quantum computer can be invented. Now, for AES it's not a huge problem, right? So, AES has a 256-bit key variant, right? A longer key. If we're at two to the 256, then Grover's brings this down to two to the 128, which is not breakable, right? On a quantum or classical computer. So, it's problem solved. So, Grover's algorithm only has a marginal effect right on our ability to do um to secure systems. The bigger problem is Shor's, right? So, Shor's algorithm factors integers in polynomial time. Suppose you have a large number n and that I'm telling you that n is p times by q. So, this is fundamental to the RSA algorithm. If you don't know what p and q are, on a classical computer, it's very, very slow to determine what they are. You basically have to guess. There's a number field theory that makes it a bit faster. It's not fast, right? And so, a 2,000-bit or 4,000-bit RSA key is currently secure. Suppose there was an algorithm that could tell you what p and q were rapidly, then you can start spoofing certificates, you can start hijacking people's internet sessions, you can start decrypting any data that was secured using one of these keys or discrete logarithm problems and elliptic curve problems like the Diffie-Hellman key exchange that we talked about before, right? So, that's a much, much bigger problem, right? If such a quantum computer was invented, this would be trivially broken, and we would need to do something about that. To be absolutely clear, such a computer doesn't exist, right? I I remain skeptical as to whether we will see one in 20 or 30 years, but I'm not in charge, right? And to be fair, there's not a big chance that my house will set on fire, but I still buy house insurance just in case it does, right? There's an argument that says we should be considering this because of this sort of future proofing. There's a concept that's often talked about called harvest now, decrypt later. And this is the idea that if you were, let's say a government, right? And you wanted to break all the encryption of other governments to find out what they were up to, right? You can't do that because we can't factor this number. But if a quantum computer exists, we could. So, what we'll do is we'll sniff all of the traffic, store on a big disk, and then in 20 years, when a computer is invented that can do it, we break everything, right? So, we're we're not, by by coming up with schemes that are trying to be robust to these quantum attacks, we are not saying because they exist, we're saying but because there's a small but notable chance they might exist in 20 or 30 years. And so, why wouldn't we replace with an algorithm that at that time will shrug and go, "Don't care," right? So, that's what we have to do. Post-quantum cryptography doesn't mean we are now post-quantum, right? It means we're preparing for a world in which we might be post-quantum in the future. What use is 20-year-old information, I suppose? >> Yeah, so, I mean, that's a good question. In my case, pretty useless, right? So, you know, I go on Amazon, I buy something with my credit card details, right? Those details are long expired by the time my my passport number, anything that's sort of private to me, has long expired before any of these things could realistically break it, right? But kind of government strategy documents or military secrets or interesting experiments at Roswell in eight weather aliens I don't know. I don't really have 30-year-old secrets. But, some people might. And those people should probably think about this. As it happens, they are thinking about this. Governments are coming up with these timelines for transitioning to post-quantum algorithms. Um and so without realizing, most of us are probably using them already, right? If you go on TLS now, if you go on your on on the web, you've got to Google, for example, you will be using a hybrid key exchange that combines elliptic curves and a new algorithm called Kyber, which is a lattice-based scheme that does a key transport, right? Or key encapsulation. NIST, the National Institute for Standards and Technologies in the United States, has really been driving this forward. They started this competition in 2016. And since then, we've had various rounds where different algorithms have been submitted. They've all been tested. And we now have some winners, in inverted commas, which are starting to be ratified as standards. It's not been smooth sailing for all of the algorithms, right? This is true of most of these competitions. So, for example, there was a potential key exchange mechanism called Supersingular Isogeny Key Exchange, or SIKE. This was broken horribly in 2022. It could have been the one we use, and then someone went, "Actually, it has a huge vulnerability," right? So, we don't know, right? Some of these algorithms, they're very, very new, but untested. We cannot be sure yet. And so, we have to be very careful to roll these things out. >> These algorithms that are susceptible all seem to rely on some kind of factoring Factoring or discrete logarithms. >> do you go to avoid that? >> Yeah. So, there are a couple That's a good question. That's That's it That's precisely what we've been working on since 2016, right? There are a few dominant sta- ways of doing cryptography that we think are resilient to both classical and quantum algorithms, right? Um bearing in mind and this if this cannot, you know, be repeated enough, a quantum computer is not simply a fast regular computer, right? It has a completely different set of algorithms, many of which are not helpful for certain problems, right? So, for example, Shor's is good for integer factorization. If you wanted to use it to brute force AES, it doesn't work. It's not It's not the right algorithm, right? It just doesn't apply. We're really trying to come up with algorithms that are resistant to be specific quantum attacks rather than just the general concept of a very fast computer, right? Which is a different issue. Um so, there were a couple of They were lattices. Maybe we can do a a video that goes into more detail on lattices, right? But a lattice is a grid of uniform points like this. And I'll just give you an example of something that's hard on a lattice, right? If this is the origin down here, and I give you a point over here, I want you to tell me what the nearest lattice point is. This is extremely easy because it's it's this one, right? Or it's this one. But you can't see the lattice. And the lattice has a thousand dimensions. So, I didn't try and draw it. The problem of the shortest vector in a lattice or the closest point in a lattice, these kind of problems, there's another related problem called learning with errors, these are what underpin some of the new post-quantum schemes. And it's not because this is better than elliptic curves or it's better than RSA. It's because we do not think that lattices yield to a particular algorithm on on quantum. Now, someone might come up with such an algorithm, but they haven't done yet. There's another one based on hash functions. So, we spent quite a lot of time talking about hash functions, right? And there are signature schemes, so signature schemes for certificates that you could come up with that use the one-way property of hash functions. So, the idea is that you publish a bunch of hashes, and then when it comes time to sign and reveal your secret information, you show you reveal the original message that you hashed, right? As proof that it was you. Okay? That's a gross oversimplification, right, for those people who actually wrote this algorithm. These hash-based algorithms are also felt to be robust to quantum, right? We already talked about Grover's. If you use a 256-bit hash, you're out of reach of this unstructured search. Anything based on hashes is going to be fine. We also know that hashes are robust to classical computers. These are not magic algorithms. They're just algorithms where we don't currently know of a quantum or classical algorithm that that could beat them, right? And so, they're likely to still be standing in 30 years time. Now, the timeline is actually quite ambitious, right? The idea is that we're we're getting we're moving away from elliptic curves and we're moving away from Diffie-Hellman key exchange and equivalents within the next kind of 5 years, right? So, you know, all of those nice videos I've done on on Computerphile are going to be completely deprecated, which is, you know, well, I'll live with it. I don't develop quantum computers, right? I don't write algorithms for quantum computers. I'm not hugely interested in the timescale of a quantum computer, but the kind of way that this kind of conceivable but unlikely threat interacts with how we make decisions today is very interesting to me, right? And actually, another thing that's really interesting is that we don't know for sure there isn't a quantum algorithm. We don't know for sure there isn't a classical algorithm that can beat lattices. And so, in some sense, maybe we don't fully trust lattices, either. So, actually, modern TLS will use something like X25519, ML-KEM 768 as its key exchange mechanism, right? And I'm surprised I managed to wheel that off, right? This here, I'm going to get to change my pen, this is an elliptic curve key exchange. Normal key exchange that we've all been doing for the last 5 10 years, right? This is post-quantum. This is Kyber, right? A problem using learning with errors. And we are not convinced that in in 20 or 30 years this is going to stand up to a quantum computer. We don't know either way on this one, right? We think it probably will, but we don't know. So, use both. We do two key exchanges at the same time, one using a normal algorithm, one using a post-quantum algorithm. We append the results together and we derive our secret key from that, right? So, this all gets turned into a key, right? Which can be used for our internet key exchange. If you go on Google now using a a modern browser, you look at your security tab, this is what you will see, almost certainly, right? So, it's already being rolled out. So, anyone that goes, "Well, quantum computers don't exist." Well, or at this scale, that's true, but we're already using algorithms that hopefully won't break when they do. A really quick message about a really fun puzzle devised by Jane Street, our channel sponsor. Jane Street, as you know, are a leading international trading firm and have a huge interest in things like neural network models to drive their trading strategies. The puzzle here, available free on their website, has been created by their machine learning team and involved shuffling all 96 of its layers. You've got to kind of put it all back together like a jigsaw. Now, I'm not going to lie, I was pretty stumped by it. But, I'll include some links below so you can give it a go and maybe send in your answers. Last time I checked, fewer than 100 people had cracked it. And if this sort of thing is your cup of tea, you should also check out some of the open roles and programs at Jane Street for people just like you. I was at their New York offices just recently and well, it really looks like a dream place to work. That is a nice little piece of art, that is.