Post Quantum Cryptography - Computerphile

0:00 It's time to panic, Shawn.

0:01 We need to implement post-quantum.

0:03 Post-quantum?

0:04 Post-quantum algorithms.

0:05 All right, we should all panic, all right?

0:07 This has nothing to do with the mailbox.

0:08 This is We shouldn't panic.

0:11 We could talk about post-quantum today, right?

0:12 Post-quantum is algorithms that are robust to quantum attack, all right?

0:16 So, we have a bunch of cryptography that that underpins most of what we do,

0:21 for example, online or on any computer system, really.

0:24 And a lot of this is quite vulnerable to specific attacks

0:28 if a quantum computer was invented that was big enough, all right?

0:32 And such a computer doesn't exist today,

0:35 but we can't rule out that it wouldn't in the future.

0:38 And so, the question is, when do we panic and how much do we panic?

0:44 As of recording this video,

0:46 there's lots of companies working on quantum computers, right?

0:48 We've done some videos on quantum before.

0:50 The biggest quantum computers are somewhere around 50 cubits, all right?

0:54 Like And this is error-corrected cubits.

0:56 So, it could cubits that have some resistance

0:59 to to be sort of noise of the system.

1:01 Um Shor's algorithm, right, which is um the algorithm that factors large

1:07 integers and can solve discrete logarithms as well, right?

1:11 Kind of like the the gold standard for algorithms on a quantum computer.

1:15 To break an RSA key would need somewhere around 4,000 cubits, all right?

1:19 So, it's safe to say we are not there, all right?

1:22 There's a question as to whether we will ever be there, all right?

1:24 Or if we are going to be, what the time scale is, right?

1:28 Conservatively, the Well, no, actually, even ambitiously,

1:32 the time scale is in the order of decades, I think, right?

1:35 But, you know, we may be here in 30 years with me very gray explaining to you,

1:42 and you've got a bit old, so you're shaking the camera around.

1:44 Even more.

1:45 Yeah.

1:45 And say, you know, we're still 30 years off this quantum thing.

1:47 What a waste of time that was, right?

1:49 I don't know.

1:50 That's what's so what's so interesting about it.

1:52 So, post-quantum is not about, "Oh, no,

1:55 there's a there's a quantum computer." It's,

1:57 there's a small chance of a quantum computer.

1:59 Can we make some informed decisions about this?

2:01 There are two quantum algorithms that we could just briefly mention, right?

2:04 There's Grover's algorithm.

2:06 And Grover's algorithm takes a search problem and square roots the run time.

2:12 Suppose you're trying to break an AES key.

2:14 And your AES key is 128-bits.

2:17 Now, on a classical computer,

2:18 you would do two to the 128 operations to brute force that.

2:23 You would guess a key, does it work?

2:24 No.

2:25 Guess a key, does it work?

2:26 No.

2:26 All right, and you just keep going.

2:28 This is very, very slow.

2:29 Grover's square roots this, right?

2:31 So, the actual search space will be two to the 64.

2:34 Now, two to the 64 is kind of within reach, right?

2:36 So, that's getting a little bit uncomfortable

2:38 if such a quantum computer can be invented.

2:40 Now, for AES it's not a huge problem, right?

2:42 So, AES has a 256-bit key variant, right?

2:46 A longer key.

2:47 If we're at two to the 256,

2:49 then Grover's brings this down to two to the 128, which is not breakable, right?

2:53 On a quantum or classical computer.

2:55 So, it's problem solved.

2:56 So, Grover's algorithm only has a marginal effect right

2:59 on our ability to do um to secure systems.

3:04 The bigger problem is Shor's, right?

3:05 So, Shor's algorithm factors integers in polynomial time.

3:10 Suppose you have a large number n and that I'm

3:13 telling you that n is p times by q.

3:16 So, this is fundamental to the RSA algorithm.

3:18 If you don't know what p and q are,

3:21 on a classical computer, it's very, very slow to determine what they are.

3:25 You basically have to guess.

3:26 There's a number field theory that makes it a bit faster.

3:28 It's not fast, right?

3:30 And so, a 2,000-bit or 4,000-bit RSA key is currently secure.

3:35 Suppose there was an algorithm that could tell you what p and q were rapidly,

3:39 then you can start spoofing certificates,

3:42 you can start hijacking people's internet sessions,

3:44 you can start decrypting any data that was

3:48 secured using one of these keys or discrete

3:50 logarithm problems and elliptic curve problems like the Diffie-Hellman

3:53 key exchange that we talked about before, right?

3:56 So, that's a much, much bigger problem, right?

3:58 If such a quantum computer was invented, this would be trivially broken,

4:02 and we would need to do something about that.

4:04 To be absolutely clear, such a computer doesn't exist, right?

4:07 I I remain skeptical as to whether we will see one in 20 or 30 years,

4:12 but I'm not in charge, right?

4:13 And to be fair, there's not a big chance that my house will set on fire,

4:18 but I still buy house insurance just in case it does, right?

4:21 There's an argument that says we should be

4:23 considering this because of this sort of future proofing.

4:26 There's a concept that's often talked about called harvest now, decrypt later.

4:30 And this is the idea that if you were, let's say a government, right?

4:32 And you wanted to break all the encryption of other

4:35 governments to find out what they were up to, right?

4:37 You can't do that because we can't factor this number.

4:40 But if a quantum computer exists, we could.

4:42 So, what we'll do is we'll sniff all of the traffic, store on a big disk,

4:47 and then in 20 years,

4:48 when a computer is invented that can do it, we break everything, right?

4:53 So, we're we're not, by by coming up with schemes that are

4:58 trying to be robust to these quantum attacks,

5:01 we are not saying because they exist,

5:04 we're saying but because there's a small but notable

5:07 chance they might exist in 20 or 30 years.

5:10 And so, why wouldn't we replace with an algorithm

5:12 that at that time will shrug and go, "Don't care," right?

5:16 So, that's what we have to do.

5:17 Post-quantum cryptography doesn't mean we are now post-quantum, right?

5:21 It means we're preparing for a world

5:23 in which we might be post-quantum in the future.

5:26 What use is 20-year-old information, I suppose?

5:29 Yeah, so, I mean, that's a good question.

5:30 In my case, pretty useless, right?

5:32 So, you know, I go on Amazon,

5:34 I buy something with my credit card details, right?

5:36 Those details are long expired by the time my my passport number,

5:40 anything that's sort of private to me,

5:42 has long expired before any of these things could realistically break it, right?

5:46 But kind of government strategy documents or military secrets or interesting

5:51 experiments at Roswell in eight weather aliens I don't know.

5:54 I don't really have 30-year-old secrets.

5:58 But, some people might.

5:59 And those people should probably think about this.

6:01 As it happens, they are thinking about this.

6:03 Governments are coming up with these timelines

6:06 for transitioning to post-quantum algorithms.

6:10 Um and so without realizing, most of us are probably using them already, right?

6:15 If you go on TLS now,

6:16 if you go on your on on the web, you've got to Google, for example,

6:19 you will be using a hybrid key exchange

6:21 that combines elliptic curves and a new algorithm called Kyber,

6:25 which is a lattice-based scheme that does a key transport, right?

6:29 Or key encapsulation.

6:30 NIST, the National Institute for Standards

6:32 and Technologies in the United States, has really been driving this forward.

6:35 They started this competition in 2016.

6:39 And since then, we've had various

6:41 rounds where different algorithms have been submitted.

6:43 They've all been tested.

6:45 And we now have some winners, in inverted commas,

6:48 which are starting to be ratified as standards.

6:51 It's not been smooth sailing for all of the algorithms, right?

6:53 This is true of most of these competitions.

6:55 So, for example, there was a potential key

6:59 exchange mechanism called Supersingular Isogeny Key Exchange, or SIKE.

7:03 This was broken horribly in 2022.

7:06 It could have been the one we use,

7:08 and then someone went, "Actually, it has a huge vulnerability," right?

7:12 So, we don't know, right?

7:13 Some of these algorithms, they're very, very new, but untested.

7:16 We cannot be sure yet.

7:18 And so, we have to be very careful to roll these things out.

7:21 These algorithms that are susceptible all seem to rely

7:24 on some kind of factoring Factoring or discrete logarithms.

7:27 do you go to avoid that?

7:29 Yeah.

7:29 So, there are a couple That's a good question.

7:31 That's That's it That's precisely what we've been working on since 2016, right?

7:36 There are a few dominant sta- ways of doing cryptography

7:41 that we think are resilient to both classical and quantum algorithms, right?

7:46 Um bearing in mind and this if this cannot, you know,

7:48 be repeated enough, a quantum computer is

7:50 not simply a fast regular computer, right?

7:53 It has a completely different set of algorithms,

7:56 many of which are not helpful for certain problems, right?

7:58 So, for example, Shor's is good for integer factorization.

8:02 If you wanted to use it to brute force AES, it doesn't work.

8:05 It's not It's not the right algorithm, right?

8:06 It just doesn't apply.

8:08 We're really trying to come up with algorithms that are resistant to be specific

8:10 quantum attacks rather than just the general

8:13 concept of a very fast computer, right?

8:15 Which is a different issue.

8:16 Um so, there were a couple of They were lattices.

8:19 Maybe we can do a a video that goes into more detail on lattices, right?

8:23 But a lattice is a grid of uniform points like this.

8:26 And I'll just give you an example of something that's hard on a lattice, right?

8:30 If this is the origin down here, and I give you a point over here,

8:35 I want you to tell me what the nearest lattice point is.

8:37 This is extremely easy because it's it's this one, right?

8:40 Or it's this one.

8:41 But you can't see the lattice.

8:42 And the lattice has a thousand dimensions.

8:44 So, I didn't try and draw it.

8:45 The problem of the shortest vector in a lattice

8:49 or the closest point in a lattice, these kind of problems,

8:53 there's another related problem called learning with errors,

8:55 these are what underpin some of the new post-quantum schemes.

8:59 And it's not because this is better

9:01 than elliptic curves or it's better than RSA.

9:04 It's because we do not think that lattices

9:06 yield to a particular algorithm on on quantum.

9:09 Now, someone might come up with such an algorithm, but they haven't done yet.

9:12 There's another one based on hash functions.

9:14 So, we spent quite a lot of time talking about hash functions, right?

9:18 And there are signature schemes,

9:19 so signature schemes for certificates that you could come

9:21 up with that use the one-way property of hash functions.

9:26 So, the idea is that you publish a bunch of hashes,

9:29 and then when it comes time to sign and reveal your secret information,

9:33 you show you reveal the original message that you hashed, right?

9:37 As proof that it was you.

9:38 Okay?

9:38 That's a gross oversimplification, right,

9:40 for those people who actually wrote this algorithm.

9:43 These hash-based algorithms are also felt to be robust to quantum, right?

9:47 We already talked about Grover's.

9:49 If you use a 256-bit hash, you're out of reach of this unstructured search.

9:55 Anything based on hashes is going to be fine.

9:57 We also know that hashes are robust to classical computers.

9:59 These are not magic algorithms.

10:01 They're just algorithms where we don't currently know of a quantum

10:05 or classical algorithm that that could beat them, right?

10:08 And so, they're likely to still be standing in 30 years time.

10:12 Now, the timeline is actually quite ambitious, right?

10:15 The idea is that we're we're getting

10:17 we're moving away from elliptic curves and we're

10:19 moving away from Diffie-Hellman key exchange and equivalents

10:23 within the next kind of 5 years, right?

10:25 So, you know, all of those nice videos I've

10:27 done on on Computerphile are going to be completely deprecated,

10:30 which is, you know, well, I'll live with it.

10:32 I don't develop quantum computers, right?

10:34 I don't write algorithms for quantum computers.

10:36 I'm not hugely interested in the timescale of a quantum computer,

10:39 but the kind of way that this kind of conceivable but unlikely threat

10:45 interacts with how we make decisions today is very interesting to me, right?

10:49 And actually, another thing that's really interesting is that we

10:52 don't know for sure there isn't a quantum algorithm.

10:54 We don't know for sure there isn't a classical algorithm that can beat lattices.

10:57 And so, in some sense, maybe we don't fully trust lattices, either.

11:01 So, actually, modern TLS will use something like X25519,

11:09 ML-KEM 768 as its key exchange mechanism, right?

11:17 And I'm surprised I managed to wheel that off, right?

11:19 This here, I'm going to get to change my pen,

11:22 this is an elliptic curve key exchange.

11:25 Normal key exchange that we've all been doing for the last 5 10 years, right?

11:29 This is post-quantum.

11:31 This is Kyber, right?

11:32 A problem using learning with errors.

11:34 And we are not convinced that in in 20 or 30

11:37 years this is going to stand up to a quantum computer.

11:39 We don't know either way on this one, right?

11:41 We think it probably will, but we don't know.

11:43 So, use both.

11:44 We do two key exchanges at the same time,

11:45 one using a normal algorithm, one using a post-quantum algorithm.

11:49 We append the results together and we derive our secret key from that, right?

11:52 So, this all gets turned into a key, right?

11:56 Which can be used for our internet key exchange.

12:00 If you go on Google now using a a modern browser, you look at your security tab,

12:05 this is what you will see, almost certainly, right?

12:07 So, it's already being rolled out.

12:09 So, anyone that goes, "Well,

12:10 quantum computers don't exist." Well, or at this scale,

12:13 that's true, but we're already using algorithms

12:16 that hopefully won't break when they do.

12:18 A really quick message about a really fun puzzle devised by Jane Street,

12:23 our channel sponsor.

12:24 Jane Street, as you know,

12:25 are a leading international trading firm and have a huge interest

12:28 in things like neural network models to drive their trading strategies.

12:33 The puzzle here, available free on their website,

12:36 has been created by their machine learning team

12:39 and involved shuffling all 96 of its layers.

12:41 You've got to kind of put it all back together like a jigsaw.

12:44 Now, I'm not going to lie, I was pretty stumped by it.

12:47 But, I'll include some links below so you can

12:49 give it a go and maybe send in your answers.

12:52 Last time I checked, fewer than 100 people had cracked it.

12:56 And if this sort of thing is your cup of tea,

12:58 you should also check out some of the open roles

13:00 and programs at Jane Street for people just like you.

13:04 I was at their New York offices just recently and well,

13:08 it really looks like a dream place to work.

13:12 That is a nice little piece of art, that is.