Microsoft Research Podcast - 094 - News from the front in the post-quantum crypto wars with Dr. Craig Costello

Episode Date: October 16, 2019

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. https://www.microsoft.com/research

As cryptographers, our job is to try to anticipate. So let's say even if it is a 10% chance that in 10 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. 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. 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. Craig Costello, welcome to the podcast.

Thanks for having me. You're a researcher on the security and cryptography team at Microsoft Research. You're a mathematician by training. Yep. 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. We'll get you up in the morning. I'd like to be able to say it's for 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. 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? Yeah, okay. 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. 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 to establish a secure channel, even if the physical channel that we're sending information over is the internet, which we assume is basically in the eyes of the other 7 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. 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 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. Right. 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 50 years ago,

we would have had to have met up in person and I would have had to hand you my shared key on paper or 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. 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? 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? 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. 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. And then once we establish that shared key, we feed it into

the old school symmetric key algorithms to do things much more efficiently. person that I'm talking to. And then once we establish that shared key, we feed it into the old school symmetric key algorithms to do things much more efficiently. Interesting. All right. So of those two cornerstones, you fall on one particular rock. Yeah, absolutely. What is it? Talk about that. 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. 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 10 years down the line or 20 years down the line, however long we want our digital information to be secure for. We have to kind of try to anticipate and guess what attackers

might rear their heads in in the years to come. 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? The two examples that I cite in the talk are ones that there's been a few movies made about both, I guess. I've watched them all. 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 I 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's what I remember trying to send notes around in primary school. We all did that. 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. Right. 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. Yeah. 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 it. We'll try. Listen, hangman and wheel of fortune. Yeah, exactly. 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 code makers 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 codebreakers 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. Right. 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. So that was in the 40s. Yeah. Things have come even further from that. 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. 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 so nowadays to protect the internet and to protect these billions of 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 internet. In the 70s, 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 70s 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. And come up with the answer. 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. Right. Yeah. They've got to be the two bigger, the prime numbers. That's what I would have done. Yeah. Yeah, indeed. One times 851. Yeah. That's one solution to the 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 smartphone. 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. 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 it promising? And how is it keeping cryptographers busy today?

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 the 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 that 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. 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. 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. We're gonna, and we do. I've heard everywhere from 30 years to a few years to, quote unquote, they secretly already exist and they're just not telling us, right? But you said the more relevant point is that regardless of where we are in that timeline, that it might already be too late. Yeah, exactly. Tell us why. 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 50 years off at least or 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 10% chance that in 10 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 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. 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 gonna happen. Right. What's happening now that should make me concerned? 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 anyone like me, I guess you think, oh, what would I possibly be doing today that I need in 10 years' time? I mean, I probably won't care if someone reads my emails in 10 years' time. You haven't been on Twitter much. No, no, that's true. Or maybe my credit card numbers will have changed by then

and I don't have to worry. But if you look at military organisations and economic entities that need their trade secrets and their classified data to remain secure, you know, decades into the future, then it matters. Yeah, it matters now, because if there is that 50 percent chance that a quantum computer exists in 15 years, then there's a 50 percent chance that they're going to be in trouble if they don't figure it out today. 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. Yeah, exactly. The retroactive breaks. So then without giving the bad guys a tactical advantage, Craig, what are you doing to quantum proof my information now? 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 70s 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 Krista talked about that algorithm on there. Right. He's a pretty famous guy. Yeah, yeah. Just Peter Shor. Absolutely. Yeah, yeah. 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 the teams back in the 70s 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. Right. And we don't have one that can do this yet. Not yet, at least not at the sizes that we care about or the sizes that you and I are sending around when we send our traffic over the Internet. Well, let's talk about that for one second, because I do want to establish even today, there's one company that has a 53 qubit quantum computer that's accessible online and another one boasts like a 72 qubit but nobody's using it it's very much an in-house

thing. What would you say the number of qubits we'd need to be worried about is? 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 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. Every other day, there's someone saying, no, I've got 75 qubits. No, I've got 81 qubits, whatever it is. Then I think these papers that came out of a team here and some

other teams around the place have said, 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 fault-tolerant qubits. So these are qubits that are very stable under those 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 machines that are already there. So it's not right now, this is just the ramping up to getting something. And fault tolerant is a key word here because they're, as we said,

pretty unstable. Absolutely. 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 multiple dimension geometric numbers. You call them abstract and exotic. Yeah, yeah, yeah, they certainly are. Tell us about this space right now. 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. 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 40 years and have had no success. So the only thing we do know is that if we have a quantum computer, we can break those. So we definitely, if we're anticipating a quantum computer, need some new problems. You know you're not quantum secure. Yes. 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 McLeese crypto system, 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 field. So just big matrices of zeros and ones with a lot of equations in 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. Yeah, that seems hard enough. 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 Shaw's algorithm to factorization and so on. So there's also lattices. So lattices is from a high level, just like codes, the way we do it in cryptography, you've got a lot of equations in 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 say 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. Define how many dimensions we're talking about here. So we're talking about a lot more than two or three dimensions, like a lot more than we can draw in this three or four dimensional world. Or in a two dimensional piece of paper, we're talking 500 plus. One of the ones that our team is involved in is 1024 dimensions. How do you even wrap your brain around that? 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. So your matrices go from a two-by-two or a three-by-three matrix to a thousand-by-thousand matrix, which we can still write down easily in store, but it's just hard to picture in a three or four dimensional world. 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 in the whole party? Yeah. So there's about four or five really popular, I guess, avenues of investigation

at the moment. And so lattices and codes are definitely two of the popular ones. And 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. 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 super singular isogeny based cryptography or SIDH. So super singular isogeny Diffie-Hellman is what SIDH stands for. And we've built this library that does this, 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 super singular isogeny problem. It's been studied

since the 90s, 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 and what we could use them for. Where is that research now? I mean, how confident are you in what you're... Because you're making some big bets here. Yeah, exactly. 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. They're another way that public key crypto has been 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 call the supersignular 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. Really, in crypto, what we try to do is to leave these things around and make them pass the test of time. And so once enough brainy cryptanalysts have tried to break it unsuccessfully and there's been no progress or very little progress, then we start to think, okay, these things are hard enough to actually ship and to do our cryptography on. 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 across a broad spectrum of technologies and endeavors. It includes cybersecurity. And that's a place where they have competitions in this cat and mouse game. So tell me what you're doing there and what you and your team have submitted. 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 just be real.

This is a competition and everyone wants their scheme to be the one that survives. That gets standardized. Yeah, exactly. So there was, I think, 69 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 Q-Tesla, 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 1024-dimensional lattice-based scheme that some of my colleagues have been involved in proposing and pursuing. And then there's this super-singular isogeny Diffie-Hellman or super singular isogeny key encapsulation. It's called PSYCH. 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. So when you put them into this competition, how do they assess? How do they... This is the funny... Well, so what happened initially, so these 70 submissions were proposed. And then I think in the first week, somewhere between like 10 or 20 of them fell.

Did it take a cricket bat to them? Yeah, 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, 26 of the 70-odd submissions have progressed to round two. And so the four that we propose 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. It sounds like a giant case of last math standing. Yeah, exactly right. And I think that's how it should be. 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. Cryptographers are people who worry about things.

Yeah. 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 away to 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. 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. Well, tell us a little about yourself, Craig. I can tell by your accent that you're not from here.

Well, you're being Redmond. Yeah, I know. And also you told me you were Australian. So how did you wind up doing cryptography research at Microsoft Research in Redmond? Yeah, so I came to do a year of my PhD in California on a scholarship at University of California in Irvine, so UCI. 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 postdoc and I love it so much that I don't see myself leaving anytime soon. But unless they drag you by your fingers. Yeah, yeah, indeed. Who did you work with in your internships? So in my internship, there's two crypto teams here at Microsoft Research. So during my internships, I worked with Kristen Lauder and her cryptography research team. And then I was in Kristen's team with my postdoc

and since then became a full-time researcher in Brian Lamarckia's security and crypto group. As we close, and this has been delightful. Thanks for your time. 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? 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. I have one more question. What two numbers multiplied do equal 851? Yeah, so that's, I think it's one times 850. I'm cheating. That one was from my talk. It's 23 times 37. But if you gave me any other number that was about the same size, I'd have to sit here for a second. That's the humbling thing. I thought that was the point of it is that I'd have to sit here for a second. You know, I thought that was the point of it, is that you'd have to sit there for more than a second.

Craig Costello, it's been so fun. Thank you for coming in and talking about math with us. Thanks for having me. It's been a pleasure. 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 slash research.