![\"Image](\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/10\/Research_Podcast_Craig-Costello_Site_09_2019_1400x788.jpg\")
<\/h3>\n<\/h3>\nDr. Craig Costello (opens in new tab)<\/span><\/a> 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)<\/span><\/a> at Microsoft Research, Dr. Costello is among a formidable group of code makers (aka cryptographers) who make it their life\u2019s 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<\/i> exist in a quantum computing future.<\/p>\n On today\u2019s 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.<\/p>\n Craig Costello: As cryptographers, our job is to try to anticipate. So let\u2019s 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.<\/p>\n (music plays)<\/em><\/strong><\/p>\n Host: You\u2019re 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\u2019m your host, Gretchen Huizinga.<\/strong><\/p>\n 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\u2019s 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<\/em> exist in a quantum computing future.<\/strong><\/p>\n On today\u2019s 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.<\/strong><\/p>\n Host: Craig Costello, welcome to podcast.<\/strong><\/p>\n Craig Costello: Thanks for having me.<\/p>\n Host: You\u2019re a researcher on the Security and Cryptography team at Microsoft Research. You\u2019re a mathematician by training\u2026<\/strong><\/p>\n Craig Costello: Yup.<\/p>\n Host: \u2026and, by your own description, you say you\u2019re 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?<\/strong><\/p>\n Craig Costello: I\u2019d like to be able to say it\u2019s philanthropic, saving-the-world reasons, but for me it\u2019s very, very simple: I really love what I do. Since I was very, very young, I\u2019ve loved mathematics and problem solving, and so, in my adult life, I\u2019m 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\u2019m interested in, there\u2019s ways that they\u2019re 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\u2019s a really nice result that we get to, often, if we\u2019re doing our job well and if our group\u2019s doing the right things, then we get to maybe have an impact on the real world.<\/p>\n Host: Well, so you say my secrets are safe with you, and I believe you\u2026 up to a point. And maybe not for long, and we\u2019ll get to that in a minute, but let\u2019s set the stage for that. I want to talk about why, right now, I feel confident sending my private information over the internet. What\u2019s in place now, cryptographically speaking, to ensure my digital secrecy?<\/strong><\/p>\n 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\u2019re pretty sure is \u2013 and we\u2019ll get to this in a minute what I mean by \u2013 classically secure\u2026<\/p>\n Host: Yes we will.<\/strong><\/p>\n Craig Costello: \u2026but 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\u2019s 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\u2019re sending information over is the internet\u2026<\/p>\n Host: Right.<\/strong><\/p>\n Craig Costello: \u2026which, 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\u2019s one way of me knowing that it\u2019s you that I\u2019m talking to.<\/p>\n Host: Right.<\/strong><\/p>\n Craig Costello: One example that\u2019s, I guess, close to home is if that little notification comes up in the corner and says, \u201cMicrosoft would like to install a software update\u201d and you click accept, one thing that you want to know is that that software is indeed coming from Microsoft\u2026<\/p>\n Host: Right!<\/strong><\/p>\n Craig Costello: \u2026and 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.<\/p>\n Host: Right.<\/strong><\/p>\n Craig Costello: Um. And so that\u2019s digital signatures, that\u2019s 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\u2019t have to have met before so there\u2019s 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.<\/p>\n 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\u2019t public key cryptography?<\/strong><\/p>\n Craig Costello: Yeah, good question. Everything that\u2019s not public key is what we call symmetric cryptography. So public key, another term for that is asymmetric cryptography, and that\u2019s based on the fact that we don\u2019t start out sharing any shared key. And then there\u2019s 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.<\/p>\n Host: Okay.<\/strong><\/p>\n 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\u2019s the right person that I\u2019m talking to\u2026<\/p>\n Host: Right.<\/strong><\/p>\n Craig Costello: \u2026and then once we establish that shared key, we feed it into the old school, symmetric key algorithms to do things much more efficiently.<\/p>\n Host: Interesting. All right so of those two cornerstones, you fall on one particular rock.<\/strong><\/p>\n Craig Costello: Yeah absolutely well so\u2026<\/p>\n Host: What is it? Talk about that.<\/strong><\/p>\n Craig Costello: \u2026so 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\u2019s a subtle difference between the models of security you might consider in key exchange and signatures. So, if we\u2019re talking about signatures, you and I really only need to worry about the adversary that exists today.<\/p>\n Host: Right now.<\/strong><\/p>\n Craig Costello: If you send me your digital signature, as soon as I verify that it\u2019s yours, then I\u2019m done with the signature. I know that today, that was you, and I\u2019m talking to you. In key exchange it\u2019s 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\u2019t 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\u2026<\/p>\n Host: Right.<\/strong><\/p>\n Craig Costello: \u2026we have to kind of try to anticipate and guess what attackers might rear their heads in the years to come.<\/p>\n Host: You\u2019ve 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 20<\/strong>th<\/sup><\/strong> century to give cryptographers a decisive advantage?<\/strong><\/p>\n Craig Costello: The two examples that I cite in the talk are ones that there\u2019s been a few movies made about both I guess so, uh\u2026<\/p>\n Host: Right, I\u2019ve watched them all.<\/strong><\/p>\n 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\u2019t 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\u2019s what I remember trying to send notes around in primary school, so\u2026<\/p>\n Host: Right, we all did that.<\/strong><\/p>\n Craig Costello: Yeah, exactly. So I\u2019m going to always replace the letter A with the letter X. And instead of the letter B, I\u2019ll replace the letter B with the letter K\u2026 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\u2019s going to be an E and we\u2019ll try\u2026<\/p>\n Host: Listen\u2026 Hangman and Wheel of Fortune!<\/strong><\/p>\n Craig Costello: Yeah exactly, yeah. And so, very soon, that became something that we wouldn\u2019t 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\u2019s 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\u2026 he\u2019s also the same guy that invented the modern computer\u2026<\/p>\n Host: Right.<\/strong><\/p>\n Craig Costello: \u2026but he built a machine and used it to break the Enigma code. And so very soon we kind of discovered that symmetric\u2026 or at least historically, we can look back and think that symmetric cryptography doesn\u2019t really solve the problem of parties having to share a secret key in advance.<\/p>\n Host: OK. So that was in the forties\u2026<\/strong><\/p>\n Craig Costello: Yeah.<\/p>\n Host: Things have come even further from that\u2026<\/strong><\/p>\n 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\u2019t really scale.<\/p>\n Host: No!<\/strong><\/p>\n Craig Costello: And certainly it doesn\u2019t 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\u2019s 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\u2026<\/p>\n Host: And come up with the answer.<\/strong><\/p>\n Craig Costello: \u2026exactly. But if I gave you the answer first and said, what were those two numbers, and now you\u2019re not allowed to choose one and the number itself, that\u2019s cheating, that\u2019s yeah, they\u2019ve got to be the two bigger, the prime numbers\u2026<\/p>\n Host: That\u2019s what I would have done.<\/strong><\/p>\n Craig Costello: Yeah, yeah indeed.<\/p>\n Host: 1 times 851.<\/strong><\/p>\n Craig Costello: Yeah. That\u2019s one solution to factorization but it\u2019s not the one we\u2019re looking for, we\u2019re 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\u2019s using a secure protocol, you\u2019re probably multiplying two numbers together or computing some exponentiation in a discrete group and\u2026<\/p>\n Host: Let\u2019s stay in the 20<\/strong>th<\/sup><\/strong> century for a minute, but move over to a different scientific field of physics \u2013 more specifically quantum physics \u2013 and the bunch of 20<\/strong>th<\/sup><\/strong> 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?<\/strong><\/p>\n 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\u2019ve 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\u2019s going on at tiniest level that we can now observe, but we couldn\u2019t observe back in the days of Newton and Galileo and so on. So at the beginning of the 20th<\/sup> 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\u2019t really apply at that subatomic level. There\u2019s a lot more weird and wacky behavior happening down there. Where quantum computing comes in is heading towards the end of the 20th<\/sup> century when physicists, and those with access to classical computers, they were trying to simulate what molecules and particles are doing. If you\u2019re trying to simulate a complex molecule and you add just one electron to a molecule that\u2019s already very complex in nature, you add one electron and another electron might either be spin up or spin down\u2026 that electron\u2019s 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.<\/p>\n Host: Right.<\/strong><\/p>\n 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.<\/p>\n Host: Right. <\/strong><\/p>\n (music plays)<\/em><\/strong><\/p>\n Host: Let\u2019s talk about how it relates to you, in cryptography, right now, and the math behind quantum code making and code breaking. People speculate when<\/em> we\u2019re going to have a functional cryptographically relevant quantum computer, but nobody ever says if<\/em>, right?<\/strong><\/p>\n Craig Costello: Yeah.<\/p>\n Host: We\u2019re going to and we do. I\u2019ve heard everywhere from thirty years to a few years to \u201cthey secretly already exist and they\u2019re just not telling us\u201d right?<\/strong><\/p>\n Craig Costello: Indeed, yeah.<\/p>\n Host: But you\u2019ve said the more relevant point is that regardless of where we are in that timeline, that it might already be too late.<\/strong><\/p>\n Craig Costello: Yeah exactly so\u2026<\/p>\n Host: Tell us why.<\/strong><\/p>\n Craig Costello: \u2026yeah, so I should say that I don\u2019t really have any authority to comment when I think a quantum computer will exist. As I said, I\u2019m 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\u2019re fifty years off at least, or they might never exist, they can\u2019t say that with certainty. And I think, as cryptographers, our job is to try to anticipate. So let\u2019s 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\u2019s 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\u2019re 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.<\/p>\n 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\u2019s say it\u2019s going to happen. What\u2019s happening now that should make me concerned?<\/strong><\/p>\n 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\u2019s secret traffic. It\u2019s 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\u2019re worried about is attackers that are already anticipating this possibility and storing today\u2019s traffic and waiting for that quantum computer to come down the line. If you\u2019re anyone like me, I guess, you think, oh, what would I possibly be doing today that\u2026<\/p>\n Host: Anyone cares about.<\/strong><\/p>\n Craig Costello: Yeah, in ten years\u2019 time. I mean, I probably won\u2019t care if someone reads my emails in ten years times or maybe\u2026<\/p>\n Host: You haven\u2019t been on Twitter much, have you?<\/strong><\/p>\n Craig Costello: No, that\u2019s true, yeah! Or maybe my, um, credit card numbers will have changed by then, and I don\u2019t 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\u2026<\/p>\n Host: It matters.<\/strong><\/p>\n Craig Costello: Yeah it matters now, because, if there is that 50% chance that a quantum computer exists in fifteen years, then there\u2019s a 50% chance that they\u2019re going to be in trouble if they don\u2019t figure it out today.<\/p>\n Host: Well, yeah and your colleague Brian LaMacchia also was on the podcast and he referred to it as \u201crecord now, break later\u201d or \u201crecord now and exploit later.\u201d<\/strong><\/p>\n Craig Costello: Yeah, exactly. The retroactive breaks.<\/p>\n Host: So then, without giving the bad guys a tactical advantage Craig, what are you doing to quantum-proof my information now?<\/strong><\/p>\n 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\u2019s Algorithm, and I believe both Brian and Krysta talked about that algorithm on their\u2026<\/p>\n Host: Right. He\u2019s a pretty famous guy\u2026<\/strong><\/p>\n Craig Costello: Yeah, yeah, absolutely\u2026<\/p>\n Host: \u2026this Peter Shor.<\/strong><\/p>\n Craig Costello: Yeah, yeah. Um, he already developed this algorithm that said, you know, if a quantum computer exists, then here\u2019s the algorithm you can use to break the integer factorization problem, but, more generally, what we call the hidden subgroup problem. And so, it\u2019s both integer factorization and<\/em> the discrete logarithm problem, they fall under the umbrella of this more general problem that Shor\u2019s 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\u2019s easy to break with a quantum computer. Now, of course they couldn\u2019t have foreseen this because quantum computing, as a topic, didn\u2019t even exist then.<\/p>\n Host: Right, and we don\u2019t have one that can do this yet.<\/strong><\/p>\n 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\u2026<\/p>\n Host: Let\u2019s talk about that for one second because I do want to establish, even today\u2026 There\u2019s one company that has a fifty three qubit quantum computer that\u2019s accessible online, and another one boasts, like, a seventy two qubit\u2026<\/strong><\/p>\n Craig Costello: Right. Yup.<\/p>\n Host: But nobody\u2019s using it. It\u2019s very much an in-house thing. What would you say the number of cubits we\u2019d need to be worried about, is?<\/strong><\/p>\n Craig Costello: It\u2019s a question that a lot of researchers are looking into and there\u2019s 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\u2019d 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\u2019s not the right metric to be looking at. But certainly, in the news, that\u2019s the thing that we look at, you know. Every other day there\u2019s someone saying no, I\u2019ve got seventy five qubits\u2026 no, I\u2019ve got eighty one qubits, whatever it is.<\/p>\n Host: Right.<\/strong><\/p>\n 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\u2019re 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\u2019s a big explosion which could happen any day, where someone figures out a way to scale this up \u2013 and I know that there\u2019s researchers here and all around the place trying to do that \u2013 but until that happens, the numbers that we use are still kind of out of the reach of these\u2026<\/p>\n Host: All right.<\/strong><\/p>\n Craig Costello: \u2026these machines that are already there.<\/p>\n Host: So it\u2019s not\u2026 right now, this is just the ramping up to getting something, and fault tolerant is a key word here\u2026<\/strong><\/p>\n Craig Costello: Yeah.<\/p>\n Host: \u2026because they\u2019re, as we said, pretty unstable.<\/strong><\/p>\n Craig Costello: Absolutely.<\/p>\n Host: Well, talk a little bit, Craig, about the kinds of problems then, that even quantum couldn\u2019t break and the kinds of things you\u2019re working on in the wacky, wacky math world of you know\u2026<\/strong><\/p>\n Craig Costello: Yeah, post-quantum cryptography.<\/p>\n Host: \u2026multiple dimension geometric numbers.<\/strong><\/p>\n Craig Costello: Yeah.<\/p>\n Host: You called them abstract and exotic.<\/strong><\/p>\n Craig Costello: Yeah, yeah, yeah they certainly are, um\u2026<\/p>\n Host: Tell us about this space right now.<\/strong><\/p>\n Craig Costello: The reason I say they\u2019re abstract and exotic, because a lot of these math problems come from the field of abstract algebra. In looking at post-quantum cryptography we\u2019re looking for mathematical problems that still do the same functionality that we already use today, public key crypto \u2013 so we still want to be able to do key exchange and digital signatures \u2013 as I said, it just turns out that the two math problems we use to do that both fall victim to Shor\u2019s Algorithm. So what we\u2019re looking for is other mathematical problems that do the same thing, but, maybe, don\u2019t fall victim to Shor\u2019s Algorithm, or to any other quantum algorithm that we know. We\u2019d like to be able to say, yes, they\u2019re quantum-secure. All of these problems that we\u2019re looking at, it could turn out that they\u2019re not even classically secure. It could turn out that RSA and the discrete log problem aren\u2019t classically secure, it\u2019s just that we\u2019ve 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\u2019re anticipating a quantum computer, need some new problems.<\/p>\n Host: You know you\u2019re not quantum-secure?<\/strong><\/p>\n Craig Costello: Yes.<\/p>\n Host: Okay.<\/strong><\/p>\n Craig Costello: But some of these proposals for post-quantum crypto have been around almost as long as public key cryptography itself. So there\u2019s these proposals based on the McEliece cryptosystem which is using error-correcting codes which, for those in the know, it\u2019s kind of like, you\u2019re doing large linear algebra over the binary fields, they\u2019re 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\u2019s 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\u2019s just that we were already pretty happy with factorization and discrete logs and we\u2026<\/p>\n Host: That seems hard enough.<\/strong><\/p>\n Craig Costello: Yeah. And we didn\u2019t know about the quantum world yet, so there\u2019s problems that have been around for a while that we\u2019ve 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\u2019s nothing we\u2019ve found yet that is like Shor\u2019s Algorithm to factorization and so on. So, there\u2019s also lattices. So lattices is, from a high level, just like code, so the way we do it in cryptography, you\u2019ve got a lot of equations and a lot of unknowns, you\u2019re kind of doing linear algebra with error again. So if you have a big linear system that you\u2019re trying to solve, if there\u2019s 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\u2019re using big matrices, if you\u2019re trying to solve these problems then it turns out that there\u2019s a lot of work that\u2019s been done that shows that if you\u2019re going to try to solve one of these hard problems in many dimensions, then it\u2019s at least as hard as trying to break lattice problems in that many dimensions.<\/p>\n Host: Define how many dimensions we\u2019re talking about here.<\/strong><\/p>\n Craig Costello: Yeah, so we\u2019re 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\u2019re talking five hundred plus\u2026 One of the ones that our team is involved in is a thousand and twenty four dimensions.<\/p>\n Host: How do you\u2026 how do you even wrap your brain around that?<\/strong><\/p>\n Craig Costello: Once you get beyond three or four dimensions, you and I would find it very hard to picture, so I can\u2019t 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.<\/p>\n Host: All right.<\/strong><\/p>\n 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\u2019s just hard to picture in our three or four dimensional world.<\/p>\n Host: Yeah, yeah. All right, so let\u2019s go a little further. You talked about lattice-based. Are there other approaches to this, and what\u2019s being done now and where do you land on the whole party?<\/strong><\/p>\n Craig Costello: Yeah so there\u2019s about four or five really popular, I guess, avenues of investigation\u2026<\/p>\n Host: Okay.<\/strong><\/p>\n Craig Costello: \u2026 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\u2019s hash-based. So hash functions are something that we\u2019ve had lying around for decades as well\u2026<\/p>\n Host: Yeah.<\/strong><\/p>\n Craig Costello: \u2026and there\u2019s 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\u2019s 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\u2019ve 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\u2019s called the supersingular isogeny problem. It\u2019s been studied since the nineties but really only used in the last decade or so to build cryptography. Nowadays, we\u2019re a lot more interested in how we might try to break them, both classically and quantumly\u2026<\/p>\n Host: Right.<\/strong><\/p>\n Craig Costello: \u2026and what we could use them for.<\/p>\n Host: Where\u2019s that research now? I mean how confident are you in what you\u2019re\u2026 because you\u2019re making some big bets here!<\/strong><\/p>\n Craig Costello: Yeah, exactly so\u2026 so, well this is the thing. This is the funny game we\u2019re playing. So I guess with isogenies, it\u2019s the newer one. In my very biased opinion it\u2019s the coolest one because it uses the coolest math, I guess. In the pre-quantum crypto, we were already using elliptic curves, that they\u2019re 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\u2019re not using one fixed elliptic curve anymore, we\u2019re 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\u2019s a group homomorphism between two nodes in this graph and, at the moment, we think that jumping far enough away from, you know, you\u2019re 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\u2019s hard even if the attacker has a quantum computer. So, that\u2019s the bet we\u2019re making but, I should back up and say, that with all of these bets, there\u2019s no way we can be sure they\u2019re quantum-secure, that\u2019s for sure, but there\u2019s no way we can even be sure that they\u2019re classically secure.<\/p>\n Host: Right.<\/strong><\/p>\n 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\u2019s 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.<\/p>\n Host: Well, let\u2019s 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\u2026<\/strong><\/p>\n Craig Costello: Okay\u2026<\/p>\n Host: \u2026across a broad spectrum of technologies and endeavors\u2026<\/strong><\/p>\n Craig Costello: Yup!<\/p>\n Host: \u2026that includes cybersecurity. And that\u2019s a place where they have competitions in this cat and mouse game.<\/strong><\/p>\n Craig Costello: Yes, exactly.<\/p>\n Host: So, tell me what you\u2019re doing there, and what you and your team have submitted.<\/strong><\/p>\n Craig Costello: Yeah, so\u2026 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\u2019s trying to break everyone else\u2019s and let\u2019s\u2026<\/p>\n Host: Let\u2019s be real.<\/strong><\/p>\n Craig Costello: \u2026let\u2019s just be real this is a competition and then everyone wants their scheme to be the one that survives.<\/p>\n Host: That gets standardized.<\/strong><\/p>\n 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\u2019s team, our security and cryptography team, we were involved in four of those submissions. So we had two digital signature algorithms, they\u2019re called Picnic, which is based on zero-knowledge proofs and symmetric cryptography, and then there\u2019s qTESLA, which is a lattice-based signature scheme, so they\u2019re our two signature schemes, and then on the key exchange side, there\u2019s 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\u2019s this Supersingular Isogeny Diffie-Helman, or Supersingular Isogeny Key Encapsulation, it\u2019s called SIKE, and that\u2019s the one that I\u2019ve been working with some members of our team and some teams around the world, we\u2019re kind of driving that isogeny-based submission.<\/p>\n Host: So, when you put them into this competition, how do they assess, how do they\u2026?<\/strong><\/p>\n Craig Costello: Yeah this is the funny\u2026 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\u2026<\/p>\n Host: To take a cricket bat to them and\u2026<\/strong><\/p>\n 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\u2019s. 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\u2019re still in the running to keep trying to push these submissions forward as far as optimizing them and investigating their security. So that\u2019s where the state of the NIST process is right now.<\/p>\n Host: It sounds like a giant case of \u201clast math standing.\u201d<\/strong><\/p>\n Craig Costello: Yeah, exactly right! And I think that\u2019s how it should be.<\/p>\n (music plays)<\/em><\/strong><\/p>\n Host: This is the part of the podcast where I usually ask what keeps you up at night and I think we\u2019ve actually covered quite a bit of what could keep us up at night. <\/strong>But let me just ask, because I can\u2019t let a podcast go by without asking, what does<\/em> keep you up at night? And I know that, again, we\u2019ve talked about so many things\u2026 you cryptographers are people who worry about things.<\/strong><\/p>\n 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\u2019t lose too much sleep every day because of those problems. I think, for me, it\u2019s the very specific technical, scientific challenges is what literally keeps me up at night. It\u2019s what I love doing and so I like to stay awake and try to solve problems, which is something I\u2019ve always loved doing. Ultimately, and hopefully, if this research that our group\u2019s 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\u2019ll help me sleep better.<\/p>\n Host: Right.<\/strong><\/p>\n Craig Costello: It might make me go to sleep earlier, but until then, no. I\u2019m kind of fascinated with the technical details and then, every now and then you come up for breath, but yeah I can\u2019t say, myself, I lose too much sleep thinking about the hackers or the threat of quantum computers. I\u2019m certainly excited about the positive aspects and I\u2019m excited at what they\u2019ve done for our field which is, hopefully, one doesn\u2019t exist, and they\u2019ve 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.<\/p>\n Host: Well tell us a little about yourself, Craig. I can tell by your accent that you\u2019re 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?<\/strong><\/p>\n Craig Costello: Yeah, so I came to do a year of my PhD in California on a scholarship.<\/p>\n Host: At?<\/strong><\/p>\n 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\u2019ve never left. I then became a post doc and I love it so much that I don\u2019t see myself leaving anytime soon!<\/p>\n Host: Not unless they drag you by your fingernails\u2026<\/strong><\/p>\n Craig Costello: Yeah, yeah. Indeed!<\/p>\n Host: Who did you work with in your internship and who do you work with now?<\/strong><\/p>\n Craig Costello: So in my internship I was\u2026 there\u2019s 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\u2019s team with my postdoc, and since then, became a full-time researcher in Brian LaMacchia\u2019s Security and Crypto group.<\/p>\n Host: As we close, and this has been delightful\u2026<\/strong><\/p>\n Craig Costello: Thanks for your time.<\/p>\n Host: \u2026what would you say to aspiring researchers who might be interested in working on cryptography in a post-quantum world? What\u2019s next in the crypto wars and who do you need in your battalion?<\/strong><\/p>\n 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\u2019s very, kind of, multidisciplinary. Whether you\u2019re coming from a computer science background and you know nothing about mathematics or physics, or whether you\u2019re 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\u2019t matter where you\u2019re coming from. Cryptography could use someone from any one of those fields or probably others.<\/p>\n Host: I have one more question. What two numbers, multiplied, do<\/em> equal 851?<\/strong><\/p>\n Craig Costello: Yeah, so that\u2019s um\u2026 I think it\u2019s 1 times 851\u2026<\/p>\n Host: Oh, that\u2019s\u2026<\/strong><\/p>\n Craig Costello: It\u2019s\u2026 I\u2019m cheating. That one was from my talk. It\u2019s 23 times 37. But, um, but, uh, if\u2026<\/p>\n Host: Yeah, that was from your talk\u2026<\/strong><\/p>\n Craig Costello: \u2026if you gave me other number that was about the same size I\u2019d have to sit here for a second!<\/p>\n Host: You know\u2026<\/strong><\/p>\n Craig Costello: That\u2019s the humbling thing.<\/p>\n Host: \u2026I thought that was the point of it, is that you\u2019d have to sit there for more than a second.<\/strong><\/p>\n Craig Costello: Yeah, yeah.<\/p>\n Host: Craig Costello, it\u2019s been so fun! Thank you for coming in and talking about math with us, and crypto.<\/strong><\/p>\n Craig Costello: Thanks for having me. It\u2019s been a pleasure.<\/p>\n (music plays)<\/em><\/strong><\/p>\n 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<\/em><\/strong><\/p>\n","protected":false},"excerpt":{"rendered":" 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\u2019s work to protect the internet against adversarial code breakers (aka cryptanalysts), both those that exist today in our classical computing world, and those that\u00a0will\u00a0exist in a quantum computing future.<\/p>\n On today\u2019s 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.<\/p>\n","protected":false},"author":39507,"featured_media":615423,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"msr-url-field":"https:\/\/player.blubrry.com\/id\/50015541\/","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"categories":[240054],"tags":[],"research-area":[13561,243138,13558],"msr-region":[],"msr-event-type":[],"msr-locale":[268875],"msr-post-option":[],"msr-impact-theme":[],"msr-promo-type":[],"msr-podcast-series":[],"class_list":["post-615354","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-msr-podcast","msr-research-area-algorithms","msr-research-area-quantum","msr-research-area-security-privacy-cryptography","msr-locale-en_us"],"msr_event_details":{"start":"","end":"","location":""},"podcast_url":"https:\/\/player.blubrry.com\/id\/50015541\/","podcast_episode":"","msr_research_lab":[],"msr_impact_theme":[],"related-publications":[],"related-downloads":[],"related-videos":[],"related-academic-programs":[],"related-groups":[144840],"related-projects":[],"related-events":[],"related-researchers":[],"msr_type":"Post","featured_image_thumbnail":"Related:<\/h3>\n
\n
\nTranscript<\/h3>\n
![\"Image](\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2019\/10\/Research_Podcast_Craig-Costello_Site_09_2019_1400x788-960x540.jpg\")
","byline":"","formattedDate":"October 16, 2019","formattedExcerpt":"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…","locale":{"slug":"en_us","name":"English","native":"","english":"English"},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/615354"}],"collection":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/users\/39507"}],"replies":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/comments?post=615354"}],"version-history":[{"count":7,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/615354\/revisions"}],"predecessor-version":[{"id":896316,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/615354\/revisions\/896316"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/615423"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=615354"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/categories?post=615354"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/tags?post=615354"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=615354"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=615354"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=615354"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=615354"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=615354"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=615354"},{"taxonomy":"msr-promo-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-promo-type?post=615354"},{"taxonomy":"msr-podcast-series","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-podcast-series?post=615354"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}