News from the front in the post-quantum crypto wars with Dr. Craig Costello

Published

Image of Dr. Craig Costello for the Microsoft Research Podcast

Episode 94, October 16, 2019

Dr. Craig Costello (opens in new tab) is in the business of safeguarding your secrets. And he uses math to do it. A researcher in the Security and Cryptography group (opens in new tab) at Microsoft Research, Dr. Costello is among a formidable group of code makers (aka cryptographers) who make it their life’s work to protect the internet against adversarial code breakers (aka cryptanalysts), both those that exist today in our classical computing world, and those that will exist in a quantum computing future.

On today’s podcast, Dr. Costello gives us a battlefield update in the ongoing crypto wars; talks about different approaches to post quantum cryptography and explains why he believes isogeny-based primitives are among the most promising; and reassures us that, as long as the battle goes on, cryptographers will continue to work very hard on the very hard math they hope will protect us from hackers and attackers, even in the age of quantum computers.

Related:

Transcript

Craig Costello: As cryptographers, our job is to try to anticipate. So let’s say, even if it is a ten percent chance than in ten years, a quantum computer will exist, what they represent to us is enough of a catastrophe to invest big resources, and a lot of research and effort from the global crypto community, to try to solve the problem, just in case. Whatever the case is, we need to prepare for it.

(music plays)

Host: You’re listening to the Microsoft Research Podcast, a show that brings you closer to the cutting-edge of technology research and the scientists behind it. I’m your host, Gretchen Huizinga.

Host: Dr. Craig Costello is in the business of safeguarding your secrets. And he uses math to do it. A researcher in the Security and Cryptography group at Microsoft Research, Dr. Costello is among a formidable group of code makers (aka cryptographers) who make it their life’s work to protect the internet against adversarial code breakers (aka cryptanalysts), both those that exist today in our classical computing world, and those that will exist in a quantum computing future.

On today’s podcast, Dr. Costello gives us a battlefield update in the ongoing crypto wars; talks about different approaches to post-quantum cryptography and explains why he believes isogeny-based primitives are among the most promising; and reassures us that, as long as the battle goes on, cryptographers will continue to work very hard on the very hard math they hope will protect us from hackers and attackers, even in the age of quantum computers. That and much more on this episode of the Microsoft Research Podcast.

Host: Craig Costello, welcome to podcast.

Craig Costello: Thanks for having me.

Host: You’re a researcher on the Security and Cryptography team at Microsoft Research. You’re a mathematician by training…

Craig Costello: Yup.

Host: …and, by your own description, you say you’re in the business of safeguarding my secrets. First of all, thanks! Now, tell us how you do that, kind of broad strokes, 10,000 foot view, and why. What gets you up in the morning?

Craig Costello: I’d like to be able to say it’s philanthropic, saving-the-world reasons, but for me it’s very, very simple: I really love what I do. Since I was very, very young, I’ve loved mathematics and problem solving, and so, in my adult life, I’m very, very lucky to be able to say that I get to wake up and do that every day. The nice thing is that the sorts of problems that I’m interested in, there’s ways that they’re addressing real world problems. And the other really nice thing for me is, being here at Microsoft Research, I get to come and work with like-minded people on these problems every day. So for me, I do it for fun, but it’s a really nice result that we get to, often, if we’re doing our job well and if our group’s doing the right things, then we get to maybe have an impact on the real world.

Host: Well, so you say my secrets are safe with you, and I believe you… up to a point. And maybe not for long, and we’ll get to that in a minute, but let’s set the stage for that. I want to talk about why, right now, I feel confident sending my private information over the internet. What’s in place now, cryptographically speaking, to ensure my digital secrecy?

Craig Costello: Yeah, OK so, I guess one thing that you should take comfort in is that we know how to do cryptography in a way that we’re pretty sure is – and we’ll get to this in a minute what I mean by – classically secure…

Host: Yes we will.

Craig Costello: …but we know how to do encryption in a way that we believe is secure even if an attacker has all of the computing power on the planet, and they have the life age of the universe to try to solve the problems that your everyday encryption is based on. If it’s implemented and done properly and correctly, then we at least believe that the problems that your smartphones and laptops and computers, and all of your digital modern life is based on, are secure. Modern public key encryption allows us establish a secure channel, even if the physical channel that we’re sending information over is the internet…

Host: Right.

Craig Costello: …which, we assume, is basically, in the eyes of the other seven billion people on the planet. I guess the two cornerstones of public key cryptography are digital signatures, and that’s one way of me knowing that it’s you that I’m talking to.

Host: Right.

Craig Costello: One example that’s, I guess, close to home is if that little notification comes up in the corner and says, “Microsoft would like to install a software update” and you click accept, one thing that you want to know is that that software is indeed coming from Microsoft…

Host: Right!

Craig Costello: …and not some third party sitting in the middle. So digital signatures is a mechanism that allows us to verify, mathematically, that that software does belong to the Microsoft that I think it belongs to.

Host: Right.

Craig Costello: Um. And so that’s digital signatures, that’s one side of the coin. And then the other side of the coin is key exchange, or encryption. They kind of both achieve the same high level goal and that is that you and I, having never met, we can very quickly establish a shared key. I guess, more than fifty years ago, we would have had to have met up in person and I would have to hand you my shared key on paper or, you know, my shared key on a USB. But nowadays, we don’t have to have met before so there’s this kind of mathematical protocol or transaction that takes place that allows you and I to agree on a shared secret that, we hope, with all of the computing power on the planet, nobody can possibly figure out what that key was.

Host: So the two, kind of, cornerstones, as you say, of public key cryptography are key exchange and digital signatures. Back up. Is there any other kind of cryptography that isn’t public key cryptography?

Craig Costello: Yeah, good question. Everything that’s not public key is what we call symmetric cryptography. So public key, another term for that is asymmetric cryptography, and that’s based on the fact that we don’t start out sharing any shared key. And then there’s symmetric cryptography, which is how cryptography started which is you and I both start out maybe in the same room, we hand each other a piece of paper that we can use as our shared key and then we can go to the other side of the world and, theoretically, exchange messages using that shared key.

Host: Okay.

Craig Costello: But nowadays, in modern encryption, we still use both. We use public key to establish that shared key, so we use key exchange to do that, and we use digital signatures to be sure that it’s the right person that I’m talking to…

Host: Right.

Craig Costello: …and then once we establish that shared key, we feed it into the old school, symmetric key algorithms to do things much more efficiently.

Host: Interesting. All right so of those two cornerstones, you fall on one particular rock.

Craig Costello: Yeah absolutely well so…

Host: What is it? Talk about that.

Craig Costello: …so I guess my research in the last five years has certainly been in the key exchange realm of things. One real-world justification, I guess, for focusing more on key exchange is, there’s a subtle difference between the models of security you might consider in key exchange and signatures. So, if we’re talking about signatures, you and I really only need to worry about the adversary that exists today.

Host: Right now.

Craig Costello: If you send me your digital signature, as soon as I verify that it’s yours, then I’m done with the signature. I know that today, that was you, and I’m talking to you. In key exchange it’s a little different. You and I will establish a shared key with a key exchange mechanism, and then you and I will use that shared key to send a lot of secret data to one another. The difference in the key exchange model is that we might want to worry about attackers that don’t just exist today, but they might exist in the future. One thing that people that worry about key exchange have to worry about is not just the best attacks in the world today, but what attackers might come tomorrow, or ten years down the line, or twenty years down the line. However long we want our digital information to be secure for…

Host: Right.

Craig Costello: …we have to kind of try to anticipate and guess what attackers might rear their heads in the years to come.

Host: You’ve said, in a very entertaining TED talk, that cryptographers are the first line of defense in the war between code makers and code breakers. So give us a brief history of this war, Craig. Who has historically been winning, and what changed in the 20th century to give cryptographers a decisive advantage?

Craig Costello: The two examples that I cite in the talk are ones that there’s been a few movies made about both I guess so, uh…

Host: Right, I’ve watched them all.

Craig Costello: Yeah, right. So, I guess one of the first kind of cited uses of cryptography was Queen Mary of the Scots, way back in the 1600s. She was conspiring against Queen Elizabeth the First to actually arrange an assassination to take back her leadership of England and Scotland. And she was sending messages out of prison and obviously she couldn’t trust any of the middlemen. So what she was doing was using what we call a substitution cipher. I guess the most basic cipher you could think of it. It’s what I remember trying to send notes around in primary school, so…

Host: Right, we all did that.

Craig Costello: Yeah, exactly. So I’m going to always replace the letter A with the letter X. And instead of the letter B, I’ll replace the letter B with the letter K… so you might think of some permutation of the alphabet, or different symbols that you might replace the letters with, and so that was, I guess, one of the first uses of cryptography but it was very soon shown to be insecure. In fact Queen Elizabeth had code breakers that, what they ended up doing was some version of what we call frequency analysis. So, if you look at the English language, you know that the most common letter is E, so all her code breakers had to do was look for the most common symbol and then go, okay, maybe that’s going to be an E and we’ll try…

Host: Listen… Hangman and Wheel of Fortune!

Craig Costello: Yeah exactly, yeah. And so, very soon, that became something that we wouldn’t want to do and then things progressed from there, and over the last four to five centuries, this race between those writing the codes, the codemakers, or the cryptographers, and the code breakers or the cryptanalysts, it’s gone back and forth between both sides. So, cryptographers will improve their encryption techniques and then the code breakers, they get to work and find out ways to break it. The second example I cite in the talk was about the Enigma Code that the Nazis used in World War II. They used these complicated machines with squillions of different combinations of how the rotors could be set up and changing them every day. And then, on the other side were the British code breakers, led by Alan Turing and a bunch of others at GCHQ, that were trying to break the Enigma Code, but again, the Germans had to have a secret key that they shared every day, and they had to exchange the secret key in advance. So they had these massive code books of daily keys that they would use. And, of course, if those code books fell into the hands of the allies then they would be able to tune their own Enigma machines to decrypt the codes which they did do, but also, Alan Turing was working with his team and he built a machine… he’s also the same guy that invented the modern computer…

Host: Right.

Craig Costello: …but he built a machine and used it to break the Enigma code. And so very soon we kind of discovered that symmetric… or at least historically, we can look back and think that symmetric cryptography doesn’t really solve the problem of parties having to share a secret key in advance.

Host: OK. So that was in the forties…

Craig Costello: Yeah.

Host: Things have come even further from that…

Craig Costello: Absolutely. So I think that the lesson, in all those historical ciphers, is that the problem of having to share a secret key, it doesn’t really scale.

Host: No!

Craig Costello: And certainly it doesn’t scale to what we now know as having to protect the internet. And so nowadays, to protect the internet and to protect these billions of, you know, interactions between parties all over the place that are happening every second, we need something that scales. One good thing was that this notion of public key cryptography, it arrived, I suppose, just in time for the for the internet. In the seventies, the invention of public key cryptography came along, and that’s the celebrated Diffie-Hellman protocol that allows us to do key exchange. Public key cryptography is kind of a notion that sits above however you try to instantiate it. So public key cryptography is a way of doing things, and how you choose to do them, or what mathematical problem you might base it on, I guess, is how you instantiate public key cryptography. So initially, the two proposals that were proposed back in the seventies were what we call the discrete log problem in finite field. When you compute powers of numbers, and you do them in a finite field, you might start with a number and compute some massive power of it and then give someone the residue, or the remainder, of that number and say, what was the power that I raised this number to in the group? And the other problem is factorization, so integer factorization. So you might be able to take any two numbers you like, and multiply them on a computer, and a computer could, essentially, multiply any two numbers you like no matter how big they are…

Host: And come up with the answer.

Craig Costello: …exactly. But if I gave you the answer first and said, what were those two numbers, and now you’re not allowed to choose one and the number itself, that’s cheating, that’s yeah, they’ve got to be the two bigger, the prime numbers…

Host: That’s what I would have done.

Craig Costello: Yeah, yeah indeed.

Host: 1 times 851.

Craig Costello: Yeah. That’s one solution to factorization but it’s not the one we’re looking for, we’re looking for the two large prime numbers that multiply and give the large composite number. So these, kind of, two proposals were initially, really, the foundations on which public cryptography were built. And so nowadays we use those all the time. So we use, you and I, on your laptop and on my smart phone, these factorization and discrete log problems are built in to our everyday lives without us knowing. So when you send a text message, if it’s using a secure protocol, you’re probably multiplying two numbers together or computing some exponentiation in a discrete group and…

Host: Let’s stay in the 20th century for a minute, but move over to a different scientific field of physics – more specifically quantum physics – and the bunch of 20th century physicists who came to the cryptography party and spiked the punch bowl. Tell us about the wacky world of quantum physics, quantum mechanics and quantum computing. First of all, why is promising, and how is it keeping cryptographers busy today?

Craig Costello: Quantum physics is this breed of physics that differs from classical physics. So, as humans, we have a very good handle on classical physics, so we know what trajectory we might have to send a rocket up in space to land on the moon, and we know why our planets orbit the sun in ellipses in the way that they do. And we’ve got a good handle on all of the things that, as humans, we can see and observe and experiment on. Quantum physics is really what’s going on at tiniest level that we can now observe, but we couldn’t observe back in the days of Newton and Galileo and so on. So at the beginning of the 20th century, as scientists started to think about what was happening at the subatomic level, so the level of electrons and protons, and subatomic particles, these new problems started to rear their heads and we realized that all of the things we thought about the motion of planets and things, they don’t really apply at that subatomic level. There’s a lot more weird and wacky behavior happening down there. Where quantum computing comes in is heading towards the end of the 20th century when physicists, and those with access to classical computers, they were trying to simulate what molecules and particles are doing. If you’re trying to simulate a complex molecule and you add just one electron to a molecule that’s already very complex in nature, you add one electron and another electron might either be spin up or spin down… that electron’s interactions with all of the other electrons in the particle, to simulate that, it requires that you double the number of possibilities. So every time you might add an electron, you might double the storage required or the computation that you need to simulate that molecule on a classical computer.

Host: Right.

Craig Costello: So very, very quickly, these simulations become exponential in size, certainly exponential in terms of what a classical computer can handle and simulate. And so the genius idea that kind of sparked quantum computing, Richard Feynman and David Deutsch and others started to think okay, if this quantum behavior is so complex and so difficult to simulate classically, maybe we can flip it around and use this crazy behavior to do computation for us. Now it sounds like a very ingenious and clever way to look at things, to look at it the reverse way, but the real problem with quantum computing is being able to actually engineer these behaviors in the real world.

Host: Right. 

(music plays)

Host: Let’s talk about how it relates to you, in cryptography, right now, and the math behind quantum code making and code breaking. People speculate when we’re going to have a functional cryptographically relevant quantum computer, but nobody ever says if, right?

Craig Costello: Yeah.

Host: We’re going to and we do. I’ve heard everywhere from thirty years to a few years to “they secretly already exist and they’re just not telling us” right?

Craig Costello: Indeed, yeah.

Host: But you’ve said the more relevant point is that regardless of where we are in that timeline, that it might already be too late.

Craig Costello: Yeah exactly so…

Host: Tell us why.

Craig Costello: …yeah, so I should say that I don’t really have any authority to comment when I think a quantum computer will exist. As I said, I’m not a physicist. No one can for sure say, one way or the other, and even those who are really skeptical and say no, they’re fifty years off at least, or they might never exist, they can’t say that with certainty. And I think, as cryptographers, our job is to try to anticipate. So let’s say even if it is a ten percent chance than in ten years one will exist, what they represent to us is enough of a catastrophe to invest big resources and a lot of research and effort from the global crypto community to try to solve the problem, just in case. Whatever the case is, we need to prepare for it. That’s what our research is doing is to try to look to ways to quantum-proof our, you know, key exchange and digital signatures and our public key crypto so that we can keep doing all the things that we’re currently doing, but when a quantum computer, or if a quantum computer, comes along, or already exists, that we can do them in a way that the quantum threat is mitigated.

Host: Right. So, you know I can see that extrapolating out into the future and it could be years it could be decades; it could be a century, who knows? Or never. But, let’s say it’s going to happen. What’s happening now that should make me concerned?

Craig Costello: We might anticipate that an attacker might not have the resources or the money to build a quantum computer today. It might just be too infeasible based on the engineering and the physics of the problem. But they certainly might have the budget to have a big data storage center to be able to store enough of today’s secret traffic. It’s cheap enough to do that, and to wait until the day comes where building a quantum computer is doable enough, or doable at all, so that they can get their hands on one. And so, one thing that we’re worried about is attackers that are already anticipating this possibility and storing today’s traffic and waiting for that quantum computer to come down the line. If you’re anyone like me, I guess, you think, oh, what would I possibly be doing today that…

Host: Anyone cares about.

Craig Costello: Yeah, in ten years’ time. I mean, I probably won’t care if someone reads my emails in ten years times or maybe…

Host: You haven’t been on Twitter much, have you?

Craig Costello: No, that’s true, yeah! Or maybe my, um, credit card numbers will have changed by then, and I don’t have to worry. But if you look at military organizations and economic entities that need their trade secrets and their classified data to remain secure, you know, decades into the future then, um…

Host: It matters.

Craig Costello: Yeah it matters now, because, if there is that 50% chance that a quantum computer exists in fifteen years, then there’s a 50% chance that they’re going to be in trouble if they don’t figure it out today.

Host: Well, yeah and your colleague Brian LaMacchia also was on the podcast and he referred to it as “record now, break later” or “record now and exploit later.”

Craig Costello: Yeah, exactly. The retroactive breaks.

Host: So then, without giving the bad guys a tactical advantage Craig, what are you doing to quantum-proof my information now?

Craig Costello: I should back up and say that the reason we have to do all of this is because those two problems I spoke about earlier, the two that were chosen in the seventies to instantiate public key cryptography, it just so happens that there was this algorithm that was published in the 90s called Shor’s Algorithm, and I believe both Brian and Krysta talked about that algorithm on their…

Host: Right. He’s a pretty famous guy…

Craig Costello: Yeah, yeah, absolutely…

Host: …this Peter Shor.

Craig Costello: Yeah, yeah. Um, he already developed this algorithm that said, you know, if a quantum computer exists, then here’s the algorithm you can use to break the integer factorization problem, but, more generally, what we call the hidden subgroup problem. And so, it’s both integer factorization and the discrete logarithm problem, they fall under the umbrella of this more general problem that Shor’s Algorithm can solve with a quantum computer. So it just so happens that the two things that the teams back in the seventies chose to instantiate public key cryptography turned out to be instances of something that’s easy to break with a quantum computer. Now, of course they couldn’t have foreseen this because quantum computing, as a topic, didn’t even exist then.

Host: Right, and we don’t have one that can do this yet.

Craig Costello: Not yet. At least not at the sizes that we care about, or the sizes that you and are sending around when we send out traffic over the internet so…

Host: Let’s talk about that for one second because I do want to establish, even today… There’s one company that has a fifty three qubit quantum computer that’s accessible online, and another one boasts, like, a seventy two qubit…

Craig Costello: Right. Yup.

Host: But nobody’s using it. It’s very much an in-house thing. What would you say the number of cubits we’d need to be worried about, is?

Craig Costello: It’s a question that a lot of researchers are looking into and there’s been papers from members of our team, and others here at Microsoft Research, that are trying to get a handle on how many qubits we’d need to break the kind of cryptography that you and I are using. If you look at the qubit growth that these companies are announcing in, you know, in the last decade or so, a lot of people who know more about the physics than I do say it’s not the right metric to be looking at. But certainly, in the news, that’s the thing that we look at, you know. Every other day there’s someone saying no, I’ve got seventy five qubits… no, I’ve got eighty one qubits, whatever it is.

Host: Right.

Craig Costello: Then I think these papers that came out of a team here and some other teams around the place have said, you know, to break the discrete log problem or the elliptic curve discrete log problem or integer factorization, you’re going to need somewhere on the magnitude of thousands of fault tolerant qubits, so these are qubits that are very stable under those, you know, crazy physical conditions we were talking about earlier. And so it seems like, unless there’s a big explosion which could happen any day, where someone figures out a way to scale this up – and I know that there’s researchers here and all around the place trying to do that – but until that happens, the numbers that we use are still kind of out of the reach of these…

Host: All right.

Craig Costello: …these machines that are already there.

Host: So it’s not… right now, this is just the ramping up to getting something, and fault tolerant is a key word here…

Craig Costello: Yeah.

Host: …because they’re, as we said, pretty unstable.

Craig Costello: Absolutely.

Host: Well, talk a little bit, Craig, about the kinds of problems then, that even quantum couldn’t break and the kinds of things you’re working on in the wacky, wacky math world of you know…

Craig Costello: Yeah, post-quantum cryptography.

Host: …multiple dimension geometric numbers.

Craig Costello: Yeah.

Host: You called them abstract and exotic.

Craig Costello: Yeah, yeah, yeah they certainly are, um…

Host: Tell us about this space right now.

Craig Costello: The reason I say they’re abstract and exotic, because a lot of these math problems come from the field of abstract algebra. In looking at post-quantum cryptography we’re looking for mathematical problems that still do the same functionality that we already use today, public key crypto – so we still want to be able to do key exchange and digital signatures – as I said, it just turns out that the two math problems we use to do that both fall victim to Shor’s Algorithm. So what we’re looking for is other mathematical problems that do the same thing, but, maybe, don’t fall victim to Shor’s Algorithm, or to any other quantum algorithm that we know. We’d like to be able to say, yes, they’re quantum-secure. All of these problems that we’re looking at, it could turn out that they’re not even classically secure. It could turn out that RSA and the discrete log problem aren’t classically secure, it’s just that we’ve been trying to break them for forty years and have had no success. So, the only thing we do know is that if we have a quantum computer though, we can break those, so we definitely, if we’re anticipating a quantum computer, need some new problems.

Host: You know you’re not quantum-secure?

Craig Costello: Yes.

Host: Okay.

Craig Costello: But some of these proposals for post-quantum crypto have been around almost as long as public key cryptography itself. So there’s these proposals based on the McEliece cryptosystem which is using error-correcting codes which, for those in the know, it’s kind of like, you’re doing large linear algebra over the binary fields, they’re just big matrices of zeros and ones, with a lot of equations and a lot of unknowns, and you just add some error to these big linear equations and all of a sudden it’s very, very hard to solve. And so these problems have been around, and they could have been chosen back in the seventies, or maybe the eighties, to do public key crypto, it’s just that we were already pretty happy with factorization and discrete logs and we…

Host: That seems hard enough.

Craig Costello: Yeah. And we didn’t know about the quantum world yet, so there’s problems that have been around for a while that we’ve got a lot of confidence in, and also it just turns out that, when we look at those problems and try to attack them with the quantum computer, there’s nothing we’ve found yet that is like Shor’s Algorithm to factorization and so on. So, there’s also lattices. So lattices is, from a high level, just like code, so the way we do it in cryptography, you’ve got a lot of equations and a lot of unknowns, you’re kind of doing linear algebra with error again. So if you have a big linear system that you’re trying to solve, if there’s no error we know how to do that very quickly. But as soon as you add a little bit of error, then these problems become very hard. And when I said we’re using big matrices, if you’re trying to solve these problems then it turns out that there’s a lot of work that’s been done that shows that if you’re going to try to solve one of these hard problems in many dimensions, then it’s at least as hard as trying to break lattice problems in that many dimensions.

Host: Define how many dimensions we’re talking about here.

Craig Costello: Yeah, so we’re talking about a lot more than two or three dimensions, like a lot more than we can draw in this, uh, three or four dimensional world, or on a two dimensional piece of paper. We’re talking five hundred plus… One of the ones that our team is involved in is a thousand and twenty four dimensions.

Host: How do you… how do you even wrap your brain around that?

Craig Costello: Once you get beyond three or four dimensions, you and I would find it very hard to picture, so I can’t geometrically picture that in my head. But the way you jump from two to three dimensions on a piece of graph paper, you, numerically, can represent how you do that and then you just keep adding dimensions.

Host: All right.

Craig Costello: So, your matrices go from you know a two by two, or a three by three matrix to a thousand by thousand matrix which we can still write down easily and store but it’s just hard to picture in our three or four dimensional world.

Host: Yeah, yeah. All right, so let’s go a little further. You talked about lattice-based. Are there other approaches to this, and what’s being done now and where do you land on the whole party?

Craig Costello: Yeah so there’s about four or five really popular, I guess, avenues of investigation…

Host: Okay.

Craig Costello: … at the moment. And so lattices and codes are definitely two of the popular ones. The lattices have been used for key exchange and digital signatures, and codes does key encapsulation too. Then there’s hash-based. So hash functions are something that we’ve had lying around for decades as well…

Host: Yeah.

Craig Costello: …and there’s now public key digital signature algorithms that are based on Merkle trees, which is kind of a way of instantiating a hash-based signature proposal. And then there’s two more that are really popular. Multivariate quadratic equations is one hard problem that people are constructing digital signatures on. And then the fifth one is based on elliptic curve isogenies. So, one of the proposals that our team is looking into is this supersingular isogeny-based cryptography, or SIDH. So Supersingular Isogeny Diffie-Helman is what SIDH stands for and we’ve built this library that does this so that people can take and test and use to do, hopefully, post-quantum-secure key exchange. But underneath it is hard problems based on what’s called the supersingular isogeny problem. It’s been studied since the nineties but really only used in the last decade or so to build cryptography. Nowadays, we’re a lot more interested in how we might try to break them, both classically and quantumly…

Host: Right.

Craig Costello: …and what we could use them for.

Host: Where’s that research now? I mean how confident are you in what you’re… because you’re making some big bets here!

Craig Costello: Yeah, exactly so… so, well this is the thing. This is the funny game we’re playing. So I guess with isogenies, it’s the newer one. In my very biased opinion it’s the coolest one because it uses the coolest math, I guess. In the pre-quantum crypto, we were already using elliptic curves, that they’re another way that public key crypto was being instantiated classically, using a single elliptic curve to do discrete log-based key exchange or signatures. The difference with the post-quantum version is that we’re not using one fixed elliptic curve anymore, we’re using exponentially many elliptic curves that are all connected in what we called the supersingular isogeny graph. And so, this jumping around between many elliptic curves, the way that you do that is called an isogeny, so it’s a group homomorphism between two nodes in this graph and, at the moment, we think that jumping far enough away from, you know, you’re starting with an elliptic curve that is a node in this graph and you compute enough jumps that you believe that, for an attacker to find out what that path was, we believe that it’s hard even if the attacker has a quantum computer. So, that’s the bet we’re making but, I should back up and say, that with all of these bets, there’s no way we can be sure they’re quantum-secure, that’s for sure, but there’s no way we can even be sure that they’re classically secure.

Host: Right.

Craig Costello: Really, in crypto, what we try to do is to leave these things around and make them pass a test of time. And so once enough brainy cryptanalysts have tried to break it unsuccessfully, and there’s been, you know, no progress or very little progress, then we start to think, okay, these things are hard enough to, you know, actually ship and to do our cryptography on.

Host: Well, let’s go back to these hard problems that you propose. I want to talk about that world for a minute, because NIST, which stands for the National Institute of Standards and Technology, they say they promote innovation and industrial competitiveness…

Craig Costello: Okay…

Host: …across a broad spectrum of technologies and endeavors…

Craig Costello: Yup!

Host: …that includes cybersecurity. And that’s a place where they have competitions in this cat and mouse game.

Craig Costello: Yes, exactly.

Host: So, tell me what you’re doing there, and what you and your team have submitted.

Craig Costello: Yeah, so… well, first of all they started out by calling it a standardization process rather than a competition. But very quickly, even in their own talks, NIST were like, okay everyone’s trying to break everyone else’s and let’s…

Host: Let’s be real.

Craig Costello: …let’s just be real this is a competition and then everyone wants their scheme to be the one that survives.

Host: That gets standardized.

Craig Costello: Yeah, exactly. So there was, I think, sixty nine submissions across key exchange and digital signatures from all around the world, and our team here, Brian’s team, our security and cryptography team, we were involved in four of those submissions. So we had two digital signature algorithms, they’re called Picnic, which is based on zero-knowledge proofs and symmetric cryptography, and then there’s qTESLA, which is a lattice-based signature scheme, so they’re our two signature schemes, and then on the key exchange side, there’s Frodo, which is one of these lattice-based submissions, so this is the thousand and twenty four dimensional lattice-based scheme that some of my colleagues have been involved in proposing and pursuing. And then there’s this Supersingular Isogeny Diffie-Helman, or Supersingular Isogeny Key Encapsulation, it’s called SIKE, and that’s the one that I’ve been working with some members of our team and some teams around the world, we’re kind of driving that isogeny-based submission.

Host: So, when you put them into this competition, how do they assess, how do they…?

Craig Costello: Yeah this is the funny… well so, what happened initially, so these seventy submissions were proposed and then, I think in the first week, somewhere between, like, ten or twenty of them fell…

Host: To take a cricket bat to them and…

Craig Costello: Yeah, oh, absolutely. And so teams were, like, the day that they were announced and posted, teams were already trying to break everyone else’s. And so very quickly, the ones that had flaws, or they were insecure, or they were just based on bad math problems, they kind of fell. And then, at this stage, twenty six of the seventy-odd submissions have progressed to round two, and so the four that we proposed in our team have fortunately progressed to that second stage. So we’re still in the running to keep trying to push these submissions forward as far as optimizing them and investigating their security. So that’s where the state of the NIST process is right now.

Host: It sounds like a giant case of “last math standing.”

Craig Costello: Yeah, exactly right! And I think that’s how it should be.

(music plays)

Host: This is the part of the podcast where I usually ask what keeps you up at night and I think we’ve actually covered quite a bit of what could keep us up at night. But let me just ask, because I can’t let a podcast go by without asking, what does keep you up at night? And I know that, again, we’ve talked about so many things… you cryptographers are people who worry about things.

Craig Costello: Yup. Cryptographers, generally, we tend to be conspiracy theorists and people that are kept up at night worrying about attackers and hackers. I myself don’t lose too much sleep every day because of those problems. I think, for me, it’s the very specific technical, scientific challenges is what literally keeps me up at night. It’s what I love doing and so I like to stay awake and try to solve problems, which is something I’ve always loved doing. Ultimately, and hopefully, if this research that our group’s involved in, and that this worldwide initiative is involved in pushing forward, if it does turn out to save the day, then maybe, just maybe, that’ll help me sleep better.

Host: Right.

Craig Costello: It might make me go to sleep earlier, but until then, no. I’m kind of fascinated with the technical details and then, every now and then you come up for breath, but yeah I can’t say, myself, I lose too much sleep thinking about the hackers or the threat of quantum computers. I’m certainly excited about the positive aspects and I’m excited at what they’ve done for our field which is, hopefully, one doesn’t exist, and they’ve shaken up our research field enough for us to have all these juicy problems to look at, and then hopefully, we solve the problem in time, and everyone can still do secure communications and encryption before they arrive.

Host: Well tell us a little about yourself, Craig. I can tell by your accent that you’re not from here. Well, here being Redmond. And also you told me you were Australian, so… How did you wind up doing cryptography research at Microsoft Research in Redmond?

Craig Costello: Yeah, so I came to do a year of my PhD in California on a scholarship.

Host: At?

Craig Costello: At University of California in Irvine, so UCLI. And then I was an intern. I came here for a summer internship, I guess, so I came through the kind of usual route of being a research intern here. And then I came back the next year, knocking on the door again for another one, and then, basically I’ve never left. I then became a post doc and I love it so much that I don’t see myself leaving anytime soon!

Host: Not unless they drag you by your fingernails…

Craig Costello: Yeah, yeah. Indeed!

Host: Who did you work with in your internship and who do you work with now?

Craig Costello: So in my internship I was… there’s two crypto teams here at Microsoft Research. So during my internships I worked with Kristin Lauter and her Cryptography Research team, and then I was in Kristin’s team with my postdoc, and since then, became a full-time researcher in Brian LaMacchia’s Security and Crypto group.

Host: As we close, and this has been delightful…

Craig Costello: Thanks for your time.

Host: …what would you say to aspiring researchers who might be interested in working on cryptography in a post-quantum world? What’s next in the crypto wars and who do you need in your battalion?

Craig Costello: Oh, good question! Who do we need in our battalion is a fantastic way to put it because the one thing I really like about this field of cryptography is it’s very, kind of, multidisciplinary. Whether you’re coming from a computer science background and you know nothing about mathematics or physics, or whether you’re coming from a mathematics background, or quantum physics background, all of those backgrounds would be very useful in crypto. It helps to have a broad interest across, I guess, the spectrum but it doesn’t matter where you’re coming from. Cryptography could use someone from any one of those fields or probably others.

Host: I have one more question. What two numbers, multiplied, do equal 851?

Craig Costello: Yeah, so that’s um… I think it’s 1 times 851…

Host: Oh, that’s…

Craig Costello: It’s… I’m cheating. That one was from my talk. It’s 23 times 37. But, um, but, uh, if…

Host: Yeah, that was from your talk…

Craig Costello: …if you gave me other number that was about the same size I’d have to sit here for a second!

Host: You know…

Craig Costello: That’s the humbling thing.

Host: …I thought that was the point of it, is that you’d have to sit there for more than a second.

Craig Costello: Yeah, yeah.

Host: Craig Costello, it’s been so fun! Thank you for coming in and talking about math with us, and crypto.

Craig Costello: Thanks for having me. It’s been a pleasure.

(music plays)

To learn more about Dr. Craig Costello, and how researchers are working to keep your online secrets safe both now and in the quantum future, visit Microsoft.com/research

Continue reading

See all podcasts

Research Areas

Research Groups