What You Need to Know About Post Quantum Crypto, With Perry Loveridge
From left to right: Perry Loveridge and Cameron Boozarjomehri. Photo: Cameron Boozarjomehri
Interviewer: Cameron Boozarjomehri
Welcome to the latest installment of the Knowledge-Driven Podcast. In this series, Software Systems Engineer Cameron Boozarjomehri interviews technical leaders at MITRE who have made knowledge sharing and collaboration an integral part of their practice.
We like to think that we have cryptography figured out. It’s just something baked into how we interact online. But researchers have been vocal about the rise of quantum computers and how they may come to fundamentally undermine our assurance in cryptography (AKA the backbone of protecting all our digital interactions). Enter Perry Loveridge, the MITRE engineer paving a path towards a future where all of our digital interactions can be protected, even from quantum computers. Listen in as Perry guides us through how we do cryptography now, how quantum computers may jeopardize this status quo, and MITRE’s mission to make post quantum cryptography possible.
A resource you may be interested in reading on this topic:
Click below to listen to podcast:
| Cameron: | 00:14 | Hello everyone, and welcome to MITRE’s Knowledge-Driven Podcast, a show where I, your host, Cameron Boozarjomehri, interview brilliant minds across MITRE. Today we’ll be interviewing Perry Loveridge on what I think might be one of the coolest topics I’ve ever gotten to talk to anyone about on this podcast. Actually, Perry, why don’t you introduce yourself first? And then you can introduce this topic, and we can go from there. |
| Perry: | 00:34 | Yes sure. Thanks Cameron, I’m Perry Loveridge, I’m a space systems engineer here at MITRE, and my focus within space systems engineering has been security and cryptography. And so today we’re going to be talking about something called post-quantum cryptography. Some of you may have heard of quantum computing. If not, I’ll talk more about it in a bit, but one of the big ideas behind quantum computing is that it breaks a lot of modern encryption. And so post-quantum cryptography is how people get around that. It’s a type of encryption that is not broken by quantum computing and can function in more or less the same way as modern encryption algorithms. |
| Cameron: | 01:09 | And so, as I understand it, this isn’t just like a single problem; this was more or less an arms race. I was wondering if you could take us back to the beginning of this arms race with, I guess what I think, as I understand it, got you into this, which had to do with GPS signals themselves. So why don’t you start there, and let’s see if we can find our way back. |
| Perry: | 01:27 | Sure. So, like I said, I’m a space systems engineer, and the space system that I work on the most is GPS. So a lot of people are familiar with GPS; they think of it as the thing they use to get around with on their phones. But it’s used for a lot more than that; it’s actually a really critical piece of infrastructure. It gives you position obviously, but it also is a really big source of timing that kind of synchronizes everything in the world at a common time. And so that’s critical for the obvious things like navigating airplanes and boats on shipping, but it’s also critical for power systems on the power grid and transactions on the internet, whether those are financial transactions or just regular communications. |
| Cameron: | 02:12 | Yeah. So as I understand it, GPS satellites are literally satellites that orbit the earth, and they’re constantly blasting a signal that says, “I am here, the satellite is here,” and your phone or GPS or whatever device you have is just using those satellites to triangulate its own position on the planet. |
| Perry: | 02:29 | Right. So like you said Cameron. GPS works using triangulation. The GPS satellite tells you where it is, and if you have three of them, then you can know where you are. And if you have four of them, you know exactly where they are, and when they’re sending their signals, then you also know what time it is. And that’s really useful for synchronizing our time pretty much everywhere in the world for all kinds of communications, applications, and power grid applications, as well as navigation. By the way, are you hearing the rabbit right now? |
| Cameron: | 02:57 | I am hearing the rabbit. |
| Perry: | 02:59 | Here, let me take it away from him. |
| Cameron: | 03:00 | Actually, if you want to mention that you have a rabbit in the room causing mischief, people always like to hear animals. |
| Perry: | 03:07 | Yeah. So if you’re hearing this, this is our pet rabbit. Right now he’s found a paper bag, and he’s tearing it up under the couch right now. I’m going to negotiate taking away this bag from a rabbit. |
| Cameron: | 03:18 | What a perfect metaphor for the problem of how to deal with the negotiation of GPS signals. |
| Perry: | 03:24 | Negotiation skills at home and at work. So the issue with GPS is that, like I said, you’re broadcasting all of these signals. So that means everyone can hear it, and the way that they hear it is with these common specifications that publish for the world to see, because everyone’s allowed to use GPS. |
| Cameron: | 03:42 | Yes. An open standard as I understand it. |
| Perry: | 03:44 | Yes, exactly. So if you want to build a GPS receiver, anyone can do it; it’s no secret how you do it. The signals are no secret either. So that’s great because it provides cheap and accurate position and timing for the world, but it also makes it really easy for someone to do something called spoofing or even jamming. |
| Cameron: | 04:02 | Yeah. So let’s break down those words, I guess. Let’s start with jamming. |
| Perry: | 04:05 | So jamming is the more simple of the two. It’s really putting out a signal at a higher power around the same frequency. So it’s like if I’m standing in a room and you’re talking to me, jamming would be like the electronic equivalent of someone else coming in and screaming even louder. Spoofing is a little bit more nuanced, and it has to do with faking a GPS signal and making it so that someone thinks that they’re somewhere that they’re not or they think that it’s a different time than it really is by really carefully crafting your own GPS signals so that they do the calculations to come out with the wrong answer. |
| Cameron: | 04:42 | That’s has a huge implication for everything from like autonomous cars just on the street level, all the way to international trade. I guess something we never really think about is the fact that the GPS systems we use are weirdly insecure and if a state actor really wanted to trick someone into going into their waters as an act of aggression, but obviously I’ve entered, that might be more grandiose. I guess there’s also just the everyday implications of, I have a harder time getting around in my town or …autonomous car—It doesn’t know where it is. |
| Perry: | 05:12 | Yeah, you’ve got it exactly right. If you can even look up spoofing, this sounds like something most people have never heard before, but it happens in real life. If you Google it, you’ll find stories of airplanes being diverted over certain airspaces, shipping boats being diverted as well, and that can lead to a lot of lost time. We haven’t seen as many examples of that in kind of people’s day-to-day lives, but spoofing does happen a lot. Or at least it happens, and it has real implications. |
| Cameron: | 05:42 | But there’s a way to help prevent spoofing, which comes back to this idea of digital signatures. |
| Perry: | 05:48 | So there’s been this idea and the world of GPS for a couple of decades now to basically put a signature on the signal. And the way a signature works is you give the person sending the message, so in this case, the GPS satellite, a special key called the secret key. And then with that, they sign it in the same way that I might sign a document with my signature in a way that when receivers who have something called a public key, get the signal, they can verify that it had to have come from the GPS satellite. And so this is all based on some high-level math and the fact that you can do problems really easily, and others are harder to reverse. |
| Cameron: | 06:30 | Yeah. As I understand it, this is part of what’s called asymmetric key cryptography. This idea that you have this public private key pair where realistically, you just have to keep one key secret because the entire function is using this fancy math, one key will always be able to unencrypt what the other key encrypts in, I guess without saying it too poorly, both directions. If the private key encrypts something, and the public key decrypts it, that’s how people can know that you sent that piece of information because only you could have encrypted it. And then if someone encrypts something with the public key and you decrypt it with the private key, that means that that person knows only you could have read the message because ideally you were the only person with the ability to decrypt that message. And this encryption gets better the longer you can make the keys. So, before, we might’ve had very short key lengths up to 128 bits, but now we can go all the way to, I think, 512 bits. I’m trying to do my binary math right now. |
| Perry: | 07:28 | So you’re right off the start. The reason why they call it asymmetric is for exactly what you said. There’s that what I called the secret key, which is the only one you have to keep secret, but there’s also a public key. So you have different people who have different things; it’s asymmetric. As far as the key sizes go, 128 bit tends to be for symmetric encryption. |
| Cameron: | 07:50 | Yeah. And symmetric just means that you only have one key this time, where asymmetric, we had to deal with two keys. Symmetric means you and I both have one key and we can use it to encrypt it and decrypt it. But this also means that there’s a high possibility someone else could have copied the key when we were exchanging them and be able to listen in on our conversations. |
| Perry: | 08:08 | Right. So with only symmetric encryption, you have to establish the same key on both sides, and you have to be confident that only the people you want to have it, have it. |
| Cameron: | 08:17 | But what you’re saying, I guess, is the different keys, depending on how secure they need to be, how unbreakable… because people can eventually figure out any key by trying all the possible combinations. That’s why [the] longer the key is, the more combinations they’ll have to try and therefore the more secure it is before someone can break it. |
| Perry: | 08:35 | Right, and that’s the case for a symmetric key. Part of the issue is that for an asymmetric key, where you get this advantage of being able to share one of your keys with the world and still maintain security, is that you have better attacks than just brute forcing it, which is what you just described is checking all possible combinations. Because these asymmetric problems are based on the most common example, which is factoring. The problem is that quantum computers are actually capable of doing that factoring much more quickly than classical computers are. |
| Cameron: | 09:11 | And this is getting into the arms race. So before we had GPS signals, and if someone could spoof the GPS signal, that’d be a problem, so we gave keys so that they could have signatures for their signals. But now you’re saying that people can break those signatures; people can still spoof it using quantum computers. And obviously not everyone has a quantum computer, but like if I was a state level actor, if I was like a big country, I could logically build and use this kind of technology for exactly this purpose. |
| Perry: | 09:39 | Yeah, exactly. And like you said, it being an arms race, you know, 20 years ago, 40 years ago, I don’t think people were too worried about these civil signals being spoofed because it just wasn’t much of a thing. The idea of making special equipment just to convince civil airplanes that are carrying like passengers, for example, that there are somewhere that they’re not… people didn’t think about it too much, so they didn’t even think to put the security on there. And then we started to see it as more and more of an issue, which is why we’re trying to address that nowadays, and people have come up with this idea to put a signature on the signal. |
| Perry: | 10:11 | But now there’s another issue, which people wouldn’t have thought of 20 years ago, once again, where a quantum computer can actually break it. But now we’re starting to see real actors like Google and IBM are building actual quantum computers. And right now, they’re nowhere close to being able to do what we’re talking about, which is break public key encryption. But the worry is that one day they would be able to. So now people are thinking about it because it is an arms race where people come up with better attacks; they come up with ways to beat what we have right now, and we have to come up with a solution to that problem because security is never an option—It’s always got to be there. |
| Cameron: | 10:45 | And so what you’ve been working on is this post-quantum signature. This way to make signatures that, ideally, they can’t be beaten easily, if not at all. |
| Perry: | 10:55 | Yes. So the post-quantum signature is the same kind of thing, but it’s based on a different problem that quantum computers don’t really know how to solve. So I used the example earlier of factoring a number. The basic idea is that you have this public knowledge, which is a really big number, but then someone else, the sender in this case, has a secret, which is what are the two numbers that you can multiply together to get that big number. And based on the fact that it’s really hard to get the small numbers from the big number, that’s where your confidence in the digital signatures comes from. |
| Cameron: | 11:28 | But what you’re saying is that’s just one way to actually do this kind of encryption, there are lots of other equations you could use that could generate some sort of either public-private pair or some other way to encrypt data such that it can’t be defeated as easily. |
| Perry: | 11:45 | Yeah. There are all kinds of ways. Unfortunately, it just gets harder and harder to understand them. As people come up with new things, I don’t even really get most of them. But people been thinking about it for years, even before this, just to think of alternates. |
| Cameron: | 11:58 | And so I guess to understand the why these other equations are, I won’t call them quantum proof, but quantum resistant. |
| Perry: | 12:04 | I think the good distinction that you’re making there is all encryption algorithms work until someone finds a break. These ones have never been proven to be unbreakable. None of them ever have. They all work because no one knows how to break them, and that’s just the way it is. So these are resistant because no one has come up with a break for them yet, even with a quantum computer. |
| Cameron: | 12:24 | Okay. And do you know of any specific ones of these equations that are being used in practice? |
| Perry: | 12:29 | In realistic, everyday applications? No one’s exclusively using post-quantum algorithms right now. But Google, for example, has an alternate to Google Chrome, the web browser, called Google Canary, that uses some of these post-quantum algorithms to secure web applications. |
| Cameron: | 12:47 | That’s Google Canary, you said? |
| Perry: | 12:48 | Google Canary, yeah. So I think what they do is they actually secure it using both the old algorithms and the new algorithms. But they may have started doing some security with only post-quantum algorithms as well—it’s kind of there in some applications. |
| Cameron: | 13:02 | I think if I can recap to this point, you’re saying, all right, so first you have no encryption. Then you have the encryption that was working pretty well for us for a while. But now thanks to quantum, we’re moving towards this other kind of encryption. I think from what you’re describing there with Canary, it’s actually, it sounds like the solution isn’t necessarily that you need to find a new encryption that is perfect. It’s easier to just find two encryptions that were working pretty well and mix them together so that the problem becomes that much harder for any one person to solve. |
| Perry: | 13:29 | So that’s what people are doing now for stuff like internet encryption. Because on the internet, you have a lot of bandwidth and a lot of processing power. And the reason why they’re doing both instead of just trusting the post-quantum is because the post-quantum algorithms haven’t been widely used for as long. So, like I said, all of our trust comes from the fact that no one’s broken it. But we can trust more that no one’s broken it if it’s been in the spotlight for a long time. So because these post-quantum algorithms are new, we just don’t trust them as much even against classical attacks. So attacks that you can do right now with a normal computer. |
| Cameron: | 14:01 | And so I think my next question for you, based on how you’re saying this is something that just the adoption comes from familiarity and being in the spotlight…. I guess my next question is what are the challenges to adoption? As you said, some pretty smart people are working on these and they’re very complicated for even the people who know what they’re doing. So what are some of the challenges, problems, solutions you’re seeing for people who do want to work towards adopting them? |
| Perry: | 14:26 | So a big issue is that, because there are a lot of different algorithms, they come with different trade-offs. As a general rule, all post-quantum algorithms are less efficient and take more bandwidth, so you have to send more information than classical algorithms. But that changes a little bit, depending on what kind of post-quantum algorithm you’re using. So one kind might be relatively easy to do the computations for, but another one might have shorter signatures, where the signature is the information that you’re sending to confirm that it’s you sending it. So for GPS, in particular, there’s a really hard and low bandwidth limit. We’re talking between 50 to 100 bits per second, which is millions of times lower than like a regular 50-megabit internet connection. And so because of that, you have to be really careful about the kind of signature that you’re using. |
| Cameron: | 15:18 | So if I can try and help understand this, what you’re saying is like, when we think of signals, we think of like our wifi. It’s like it’s designed to get tons of data through, but GPS satellites in particular, they’re very small bandwidth. |
| Perry: | 15:31 | It can be as low as 50 bits per second. |
| Cameron: | 15:33 | And 50 bits, that’s a handful of bytes. That’s like, I can do this math, let’s say a little less than 7 bytes worth of data. So not even close to a kilobyte or a megabyte or a gigabyte numbers that we’re typically expecting. So as a result, because normally encryption can be 128 bits, that’s way bigger than what you guys are working with, so you have to find ways around the limitations of the technology itself. |
| Perry: | 15:57 | Yeah, exactly. And you just have to figure out what are the trade-offs you can make? What can you limit in the signal? How often do you need to get this signature? And can you make sure that the users you need to be able to verify a signature are able to run the algorithms that verify the signature. |
| Cameron: | 16:14 | And when it comes to encryption and cryptography, I know that some, I think Google’s most recent phone… they basically sold it on, there’s a chip inside the phone that’s dedicated just to encrypting and decrypting stuff because it’s so focused on securing your data. When I saw that, it made me think like, all right, so normally when we’re doing encryption, that’s a lot of processing power as well. It’s not just that we have to send that data. It’s that we have to be able to turn that data back into something we can actually use. So is that something else you’re seeing with certain devices—that…are they powerful enough to deal with this? Is my phone going to be able to deal with post-quantum cryptography? Am I going to need a new phone? |
| Perry: | 16:51 | For GPS in particular, because of that bandwidth limitation, digital signatures are not going to be so frequent that they should cause problems for your phone. For some things like, let’s talk about internet of things for a second. We have really small devices that are doing things like data collection, and everything else that internet of things does—I’m not an expert there. But some of these devices have really limited power. They have small batteries, it’s hard to recharge them. So if you really put in a beefy digital signature algorithm, like some of the post-quantum ones especially, that can really limit the lifetime of a device that limited to a single battery. |
| Cameron: | 17:29 | I think I’m getting it. There’s always a trade-off, not just in terms of the power needed to actually do the encryption decryption, but also the power available in your specific use case. It’s not worth it for me to put the super fancy Google beefy, quantum titan chip into a light bulb. |
| Perry: | 17:46 | Yes, exactly. It’s just like looking for housing, there are trade-offs in each algorithm. One house you’re looking at might have a better location, but the other one is going to be a little bigger or a little bit cheaper. There is no post-quantum algorithm that wins on all fronts. |
| Cameron: | 18:01 | That’s a really handy metaphor to go out on. So let me do a little recap because I know we’re short on time. We discussed GPS. Now we discussed the arms race of encryption and then post-quantum. And then we got to explore the different ways that… I think you mentioned there are a lot of different algorithms out there, but as many of them as there are, sometimes it just doesn’t make sense to use them in certain use cases, maybe with IOT [internet of things], either because of the computational power or the actual power limits. And so I think, just to go out on, is there anything else you’d like to leave us with before we go out? |
| Perry: | 18:34 | I would definitely recommend looking up more about the other applications of quantum computers, because that whole field is just fascinating and really, really new, and also something called quantum cryptography or quantum key distribution, which is a completely quantum version. So not post-quantum, but quantum version of some asymmetric cryptography applications. Like I said, it’s even over my head so I think I’m good leaving it on that. |
| Cameron: | 19:01 | Well, before we go, I would obviously like to give a big thank you to the Knowledge-Driven Enterprise at MITRE for making this conversation and this podcast possible. But more importantly, I would like to give you, Perry, a huge thank you. Like I said, I was super excited to get to have this conversation. I think the cryptography and quantum computers and now post-quantum cryptography is really cool and hopefully we’ve done a service to anyone listening to this, making this topic ideally easy enough for them to understand. I think I understand it. |
| Perry: | 19:29 | Thank you, Cameron. I could talk about this stuff all day, so I really appreciate you giving me the opportunity. |
| Cameron: | 19:33 | Hopefully we can have you back and we can have more conversations because it doesn’t sound like this topic’s going away anytime soon. |
| Perry: | 19:38 | Yeah, definitely not. |
Cameron Boozarjomehri is a Software Engineer and a member of MITRE’s Privacy Capability. His passion is exploring the applications and implications of emerging technologies and finding new ways to make those technologies accessible to the public.
© 2021 The MITRE Corporation. All rights reserved. Approved for public release. Distribution unlimited. Case number 21-0480
MITRE’s mission-driven team is dedicated to solving problems for a safer world. Learn more about MITRE.
See also:
The Best Security Against Quantum Attack Isn’t Quantum Key Distribution
Will Quantum Computers Revolutionize My Daily Life? Not in the Ways You Might Think
The Power of Geospatial Data in Developing Countries
Jen Choi and Josh LeFevre and the power of “Yes, And”
Getting Students Excited About STEM (and MITRE), with Willie Hill
Project Demodocus: Bringing Accessibility to the Masses
Turkeys vs Swans, with Imanuel Portalatin
Justin Brunelle: Lessons from MITRE’s Innovation Program
Rachel Mayer on the Fight Against Maternal Mortality