{"id":501956,"date":"2018-08-22T08:01:09","date_gmt":"2018-08-22T15:01:09","guid":{"rendered":"https:\/\/www.microsoft.com\/en-us\/research\/?p=501956"},"modified":"2019-12-09T15:29:44","modified_gmt":"2019-12-09T23:29:44","slug":"cryptography-for-the-post-quantum-world-with-dr-brian-lamacchia","status":"publish","type":"post","link":"https:\/\/www.microsoft.com\/en-us\/research\/podcast\/cryptography-for-the-post-quantum-world-with-dr-brian-lamacchia\/","title":{"rendered":"Cryptography for the post-quantum world with Dr. Brian LaMacchia"},"content":{"rendered":"<div id=\"attachment_501959\" style=\"width: 1034px\" class=\"wp-caption aligncenter\"><img loading=\"lazy\" decoding=\"async\" aria-describedby=\"caption-attachment-501959\" class=\"wp-image-501959 size-large\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-1024x576.png\" alt=\"Dr. Brian LaMacchia, Distinguished Engineer\" width=\"1024\" height=\"576\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-1024x576.png 1024w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-300x169.png 300w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-768x432.png 768w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-1066x600.png 1066w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-655x368.png 655w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-343x193.png 343w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site.png 1400w\" sizes=\"(max-width: 1024px) 100vw, 1024px\" \/><p id=\"caption-attachment-501959\" class=\"wp-caption-text\">Distinguished Engineer Dr. Brian LaMacchia. Photography by Maryatt Photography<\/p><\/div>\n<h3>Episode 38, August 22, 2018<\/h3>\n<p>You know those people who work behind the scenes to make sure nothing bad happens to you, and if they\u2019re really good, you never know who they are because nothing bad happens to you? Well, meet one of those people. <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/people\/bal\/\">Dr. Brian LaMacchia<\/a> is a Distinguished Engineer and he heads up the <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/group\/security-and-cryptography\/\">Security and Cryptography Group<\/a> at Microsoft Research. It\u2019s his job to make sure \u2013 using up-to-the-minute math \u2013 that you\u2019re safe and secure online, both now, and in the post-quantum world to come.<\/p>\n<p>Today, Dr. LaMacchia gives us an inside look at the world of cryptography and the number theory behind it, explains what happens when good algorithms go bad, and tells us why, even though cryptographically relevant quantum computers are still decades away, we need to start developing quantum-resistant algorithms right now.<\/p>\n<h3>Related:<\/h3>\n<ul type=\"disc\">\n<li><a href=\"https:\/\/www.microsoft.com\/en-us\/research\/podcast\">Microsoft Research Podcast<\/a>: View more podcasts on Microsoft.com<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/itunes.apple.com\/us\/podcast\/microsoft-research-a-podcast\/id1318021537?mt=2\">iTunes<\/a>: Subscribe and listen to new podcasts each week on iTunes<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/subscribebyemail.com\/www.blubrry.com\/feeds\/microsoftresearch.xml\">Email<\/a>: Subscribe and listen by email<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/subscribeonandroid.com\/www.blubrry.com\/feeds\/microsoftresearch.xml\">Android<\/a>: Subscribe and listen on Android<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/open.spotify.com\/show\/4ndjUXyL0hH1FXHgwIiTWU\">Spotify<\/a>: Listen on Spotify<\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/www.blubrry.com\/feeds\/microsoftresearch.xml\">RSS feed\u00a0<\/a><\/li>\n<li><a class=\"msr-external-link glyph-append glyph-append-open-in-new-tab glyph-append-xsmall\" href=\"https:\/\/note.microsoft.com\/ww-registration-microsoft-research-newsletter-s.html?wt.mc_id=S-webpage_podcast\">Microsoft Research Newsletter<\/a>:\u00a0 Sign up to receive the latest news from Microsoft Research<\/li>\n<\/ul>\n<hr \/>\n<h3>Episode transcript<\/h3>\n<p>Brian LaMacchia: We still don\u2019t really have big quantum computers. We have very tiny toy ones. But from being able to demonstrate theoretically that if a new fundamental model of computation showed up, that it would change all of our assumptions, that\u2019s yet another example of how we have to constantly think about what an attacker has available, and if the attacker\u2019s resources all of a sudden change, that means they can do more.<\/p>\n<p><strong>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<p><strong>Host: You know those people who work behind the scenes to make sure nothing bad happens to you, and if they\u2019re really good, you never know who they are because nothing bad happens to you? Well, meet one of those people. Dr. Brian LaMacchia is a Distinguished Engineer and he heads up the Security and Cryptography Group at Microsoft Research. It\u2019s his job to make sure \u2013 using up-to-the-minute math \u2013 that you\u2019re safe and secure online, both now, and in the post-quantum world to come.<\/strong><\/p>\n<p><strong>Today, Dr. LaMacchia gives us an inside look at the world of cryptography and the number theory behind it, explains what happens when good algorithms go bad, and tells us why, even though cryptographically relevant quantum computers are still decades away, we need to start developing quantum-resistant algorithms right now. That and much more on this episode of the Microsoft Research Podcast.<\/strong><\/p>\n<p><strong>(music plays)<\/strong><\/p>\n<p><strong>Host: Brian LaMacchia, welcome to the podcast.<\/strong><\/p>\n<p>Brian LaMacchia: Thank you, pleasure to be here.<\/p>\n<p><strong>Host: You\u2019re a distinguished engineer at Microsoft Research, and you head the security and cryptography team here, which you\u2019ve called the company\u2019s center of excellence for cryptography. What does your group do? What are the big questions you\u2019re asking, the big problems you\u2019re tackling? What gets you up in the morning?<\/strong><\/p>\n<p>Brian LaMacchia: We are, as I said, the Center of Cryptographic Research and Development for the company. We focus on the hardest problems that the company has that somehow involve cryptography, encryption, digital signatures, things like that. We started a decade ago, as a little cryptographic tools team, looking for places within the corporate research and development group where we could add value. And we tackled security problems and cryptographic problems for what was then grid computing and became cloud computing, our data centers and security problems all over the place. But for the last three years, we\u2019ve been focused on this primary work on the upcoming threat of quantum computers, if they\u2019re successful. But then we also do work on other security problems. We spend a lot of time working on the security of Internet of Things devices, and how do we make sure that devices inside your home can\u2019t be manipulated. We also \u2013 I have a member of my team who spends a lot of time on election security and how do you verified voting and what, how can we bring the best in cryptographic research to end-to-end verifiable elections?<\/p>\n<p><strong>Host: Well, let\u2019s do a little bit of a level set as we start here, about the field of cryptography. Can you give us a brief history of cryptography?<\/strong><\/p>\n<p>Brian LaMacchia: Sure. So, cryptography is the science of data encryption. And it actually goes back to ancient times. We know that the Romans used very simple forms of cyphers. The Caesar cypher was used to send information around. And cryptography, traditionally, was in the military field. And for the longest time, it was what we call, in the field, symmetric key cryptography. That is, if you and I wanted to exchange secret messages, we would agree on a secret password or a configuration of a mechanical device or something that we used to perform encryption. And then I would use that secret to encrypt information to you. You would get the cypher text, the encrypted information, and you\u2019d use that same secret to decrypt it, so we have the same symmetric shared secret key. And of course, in the 20th Century, cryptography started being used more and more to protect wireless communications, right? To protect radio. This is\u2026 most famously was used in World War II by all sides to protect radio communications. And your listeners probably all know the story of the German Enigma machine, which was a mechanical encryption device, which was broken. Initial research done by Polish mathematicians, and then it moved to Bletchley Park and the British did a whole bunch of work under Turing and broke the Enigma and therefore learned information in secret about encrypted communications. All of that\u2019s within the realm of the shared key model. And then there was a breakthrough for what was called public key cryptography. And the difference in public key is, each of us who wants to communicate has a pair of keys that are mathematically related \u2013 a private key and a public key \u2013 and one of those keys you can release to the world. So, if I want to encrypt something to you, I go get your public key and I encrypt it to your public key, but I can\u2019t decrypt it with your public key. You can decrypt with your private key that matches mathematically, and the same is true for me. And there\u2019s a variant of that, which is the digital signature problem, which is, I can use a private half to digitally sign a message that anybody can verify it could have only come from me. And we use both of those technologies today. Every time you open a secure connection in your browser to a website, and that\u2019s an https connection, you\u2019re doing an encryption and digital signature operation so no nefarious characters can learn your credit card number or the email you\u2019re typing if you\u2019re talking to a web email, something like that.<\/p>\n<p><strong>Host: Let\u2019s talk about algorithms. Most people take them for granted, and may even be blithely unaware that algorithms are running their lives right now in many, many ways. And I bet if you asked anyone on the street, does math have an expiration or sell by date, or can an algorithm go bad, they\u2019d just look at you like you\u2019re strange. But you\u2019ve said all cryptographic algorithms weaken, degrade, or break over time.<\/strong><\/p>\n<p>Brian LaMacchia: That\u2019s correct.<\/p>\n<p><strong>Host: Talk about that.<\/strong><\/p>\n<p>Brian LaMacchia: Okay. So, unlike many other parts of computer science and computer programming, cryptographic algorithms, which are number theory at their heart, naturally degrade over time as we learn more about how to attack them, and as we assume that our attackers have more compute power available to them. So, we grade algorithms based on security levels: how much work do we think an attacker has to put in to break an algorithm? And as we learn more over time, the security level degrades. And algorithms that we think are okay today are not okay tomorrow. And that\u2019s really important when you\u2019re writing an application or a security protocol or a computer system, to understand that the algorithms you\u2019re dependent upon today are going to have to change, and you can\u2019t just use them for the future. It doesn\u2019t necessarily have a \u201csell by\u201d date on it, but we are constantly trying to predict what an attacker can do. And sometimes, it\u2019s just more compute power being available. And sometimes there\u2019s an academic result that, all of a sudden, changes our understanding of number theory. I guess the other thing to add is, sometimes we get a prediction of when an algorithm is going to break. Like, we will see a series of work done in academia where the attacks will come along and they will make further and further progress until something breaks catastrophically. Sometimes we don\u2019t get a heads up. I can give you two stories on that, if you\u2019d like stories.<\/p>\n<p><strong>Host: I would. I like stories, and I bet our listeners do too.<\/strong><\/p>\n<p>Brian LaMacchia: Okay, so a cryptographic hash function is a function that takes any amount of input and hashes it down to a fixed digest size. And for a long time, we used one called MD-5, which was invented by Ron Rivest, a Professor Rivest MIT, the R in the RSA algorithm. And we all thought it was secure. And in 2004, at the annual US Crypto Conference, Professor Xiaoyun Wang from China got up and demonstrated two messages that had the same MD-5 hash value. And you\u2019re not supposed to ever be able to do that. And she did that. And the fact that she could do that meant that the fundamental security property of that hash function was no longer any good. And therefore, we had to move to another hash function, because that one was busted, as far as we care from a cryptographic perspective.<\/p>\n<p><strong>Host: But you didn\u2019t know that going in?<\/strong><\/p>\n<p>Brian LaMacchia: We didn\u2019t know that going in, but we knew when we heard it, that all of a sudden, we were going to get press questions the following morning. And in fact, Josh Benaloh from my team and I sat at the back of the room and wrote a 4-page Q and A for all the folks back at Microsoft to understand what this meant for our products and services going forward. We transitioned to the next hash function that we had, which we called SHA-1. But SHA-1 shared some structural properties, similarities, with MD-5, and we figured that it would only be time until SHA-1 fell. And in fact, in March of last year, Mark Stevens at CWI in the Netherlands demonstrated a SHA-1 hash collision. And now SHA-1 of course has been broken the same way MD-5 has.<\/p>\n<p><strong>Host: Talk a little bit about how you go about attacking your own stuff.<\/strong><\/p>\n<p>Brian LaMacchia: Well, first off, we assume that everything we do is out in the open. And this is sort of a fundamental thing for my group now. The algorithms themselves are open and published. The code that we ship is open source and available. And from a theoretical perspective, we assume that the attacker has access to all knowledge about the algorithm and the code and the construction. And the only thing they don\u2019t have access to is the secret piece of the key.<\/p>\n<p><strong>Host: Key.<\/strong><\/p>\n<p>Brian LaMacchia: Okay, so when we try to attack our own algorithms, we\u2019re hopefully using the same set of information and it\u2019s, how can we deduce the secret key without knowing it? That\u2019s part of the analysis and thinking up new techniques and trying them out and trying to get cost estimates for what\u2019s doable if you have a cloud-computing infrastructure at your back, and, you know, what would it cost to break something of a particular size?<\/p>\n<p><strong>(music plays)<\/strong><\/p>\n<p><strong>Host: Well, let\u2019s move onto quantum. This is a big topic, and it\u2019s basically what you\u2019ve been talking about for quite a while: life in a postquantum world. And that\u2019s still a ways out, but as they say in the movie industry, it\u2019s coming to a screen near you.<\/strong><\/p>\n<p>Brian LaMacchia: That\u2019s right.<\/p>\n<p><strong>Host: Maybe not your screen, but somebody\u2019s. And also, maybe not right away. But let\u2019s talk about what quantum computing is. I know we did a podcast with Krysta Svore who\u2019s \u201call quantum all the time.\u201d And that was her perspective. I want to hear from a cryptographer\u2019s perspective. What is it? How is it fundamentally or materially different from classical computing, and why does it matter to researchers like you, Brian?<\/strong><\/p>\n<p>Brian LaMacchia: Sure. And first off, I should point out that actually Krysta gave a great explanation of this during her podcast, and our teams actually work together. We sort of dovetail with each other. But quantum computing is a fundamentally different model of computing. And from our perspective as cryptographers, the key breakthrough in this actually happened in 1994. That was when Peter Shor at AT&T Bell Labs invented a quantum factoring algorithm. That is, he demonstrated that if you had access to a big enough quantum computer, you could solve a problem in polynomial time. That is, you could factor in polynomial time, which we do not know how to do today or anything close to that, with classical computers. Now, Peter didn\u2019t have a quantum computer. We still don\u2019t really have big quantum computers. We have very tiny toy ones. But from being able to demonstrate, theoretically, that if a new fundamental model of computation showed up, that it would change all of our assumptions, that\u2019s yet another example of how we have to constantly think about what an attacker has available, and if the attacker\u2019s resources all of a sudden change, that means they can do more. So, from a cryptographic perspective, quantum computing is yet another model of computation that opens up a different line of attack and a different set of algorithms. And for a lot of the problems that we care about today, we know that quantum computers will make the attacks faster. And for some of the types of cryptography we\u2019ve talked about, there are easy mitigations. And for some of the things we\u2019re using today, there aren\u2019t. And that\u2019s sort of what the concern is.<\/p>\n<p><strong>Host: You\u2019ve talked about a \u201cbig enough\u201d quantum computer.<\/strong><\/p>\n<p>Brian LaMacchia: Yes.<\/p>\n<p><strong>Host: Let\u2019s go there for a minute. What is big enough?<\/strong><\/p>\n<p>Brian LaMacchia: Okay, well for your listeners who might be interested, we actually had a paper that appeared at Asiacrypt last December, 2017, working with members of Krysta\u2019s team on trying to come up with precise estimates for how many logical cubits, logical quantum bits, you need for \u201cbig enough.\u201d And what we mean by that is, when I think about how difficult it is to break a cryptographic algorithm, I talk about that in terms of, how big are the keys? What\u2019s the security parameter for the algorithm? So, if I am typically doing RSA with 2-kilobit keys, 2048-bit public keys. That is the module. This is the product of 2 primes of each of about 1024 bits. How long does it take to factor that? And that is well beyond anything we could do with, sort of, all the compute power we have available to us today. But what our paper showed is that if you had just over double that number of quantum bits, just over 4096 quantum bits available in a quantum computer \u2013 and those are logical quantum bits that are stable \u2013 you can run Shor\u2019s algorithm on it, and you can factor that 2048-bit number in polynomial time. So, for the types of public key algorithms that we are using today, if we\u2019re talking about factoring, typically your RSA keys are 2 to 4 kilobits in size. And we need double that number of quantum bits, plus a little bit extra. Basically, from my perspective, things don\u2019t get interesting until there\u2019s at least 1,000 logical quantum bits around on a quantum computer, and really up to 10,000 logical quantum bits.<\/p>\n<p><strong>Host: And that is what you call a cryptographically relevant quantum computer?<\/strong><\/p>\n<p>Brian LaMacchia: Quantum computer. Cryptographically relevant. So, in our world, if it\u2019s got say, on the order of 1,000 to 10,000 logical quantum bits, and you can program it, then it becomes cryptographically relevant.<\/p>\n<p><strong>Host: Now you\u2019re going to pay attention.<\/strong><\/p>\n<p>Brian LaMacchia: And not you\u2019ve got to pay attention. That\u2019s where things get catastrophic for the public key algorithms that we\u2019re using today. Or things get very interesting. Below that, there might be other interesting problems you can solve in chemistry, metallurgy, agriculture, things like that. But what I care about is up in the 1,000 to 10,000 quantum bit range.<\/p>\n<p><strong>Host: Let\u2019s say quantum does make it big and becomes cryptographically relevant sooner than we think. What\u2019s the good news and bad news about a big breakthrough in quantum computing, in your mind?<\/strong><\/p>\n<p>Brian LaMacchia: The bad news is, it means a lot of systems that we use today have to get upgraded, and that the algorithms have to be replaced. And, pretty much, if you have or if you know that an adversary has access to a cryptographically relevant quantum computer, every commonly used public key encryption needs to be replaced. The good news is we\u2019ve actually got a bunch of candidate replacements. This is work that my team\u2019s doing, other folks around the world are doing. And in fact, the US government is running a standardization activity right now to try to pick some new \u201cquantum-resistant\u201d public key encryption and digital signature algorithms. These are classical algorithms. You don\u2019t need a quantum computer to run them. These are algorithms that run on classical computers, your laptop, my phone\u2026 They can run just like RSA and Diffie-Hellman and elliptic curve today. They\u2019re just based on different hard number theory problems for which we don\u2019t believe there is a fast quantum solution. And an important point here is, we don\u2019t have any proofs right now that the quantum-resistant algorithms that we\u2019re all investigating are guaranteed to be quantum-resistant. What we know is that there\u2019s no known quantum advantage. It\u2019s a little bit of a subtle point, but it\u2019s important, that even for the new algorithms that we and other people around the world are investigating, we don\u2019t believe having a cryptographically relevant quantum computer gives you any advantage over having just a cloud full of datacenter servers to help you. But it\u2019s different than saying, we are guaranteed that there is no fast quantum algorithm. That we don\u2019t know yet.<\/p>\n<p><strong>Host: Right. Right. Well, if we situate ourselves in a postquantum world and we\u2019re dealing with quantum-resistant algorithms, who has a vested interest in developing these, and who are the players at work here? You alluded to that just now. What\u2019s the big picture, and who\u2019s all involved?<\/strong><\/p>\n<p>Brian LaMacchia: So, there\u2019s who\u2019s designing them and then who uses them. And if you think about who uses them, well, it\u2019s anybody who ships an implementation of a cryptographic library or, you know, inside of an operating system or a device. Anybody who\u2019s trying to open a secure channel, a secure communications channel over the internet. You need to able to authenticate the party at the other end, and you need to be able to establish an encrypted channel and send encrypted information back and forth. That\u2019s just common practice, right? And as more and more of our communications are happening on the internet in general, we want all those to be encrypted and private. So, everybody who is involved in shipping code like that, one way or the other, is going to be a customer of quantum-resistant algorithms. Who\u2019s developing it? It\u2019s academic researchers and industry researchers, cryptographers around the world. My team\u2019s currently working on four different algorithms right now, and each of them is an international collaboration where we have researchers from industry and academia participating with us on each of those four. And they\u2019re different sets. And you know, there\u2019s some people that are working on one algorithm with us, and some on another. And these algorithms have different pros and cons, when compared. Some are faster than others, some have smaller key sizes than others. They have different engineering properties. And it\u2019s not clear it\u2019s a one-size-fits-all sort of thing. My guess is that when the US government standardizes these in, hopefully, five years, they\u2019ll actually choose a handful of encryption and digital signature algorithms for different use cases, because what you want to fit into that smart light switch in your phone that you don\u2019t want to be taken over by somebody, is very different than what you\u2019re going to go put into your laptop.<\/p>\n<p><strong>Host: Well, let\u2019s talk about that issue right there, the US government, among other governments. There\u2019s a competition going on that I would love for you to tell us about and what it involves and what the purpose of it is.<\/strong><\/p>\n<p>Brian LaMacchia: Sure. So, in 2015, NSA, for a decade, had been advancing the use of elliptic curve public key technology as part of a suite of commercially-available algorithms, that they called Suite B, as opposed to Suite A, which were classified algorithms, that they encouraged industry to ship to meet the needs of the US Department of Defense to protect up to top-secret-level information. NSA came out in 2015, and said, \u201cBy the way, if you haven\u2019t finished the move to elliptic curve cryptography, you should save your development cycles, because we\u2019re going to tell you to move to something quantum-resistant in the not-too-distant future.\u201d That caused the US National Institutes of Standards in Technology, or NIST, which is the standard-setting body for the United States government, not just DOD, for all government, to launch a standardization process, or a selection process, to come up with new algorithms. And NIST has led two very successful public standardization efforts in cryptography in the past, and so NIST has a history of running these types of competitions. And now they\u2019ve launched this competition. And, in fact, my team is part of four submissions of I think about 65 that made it in and are still active, although some of those have since been broken. And what happens now is we are all approved Round One candidates. And about this time next year, NIST will announce which of those move on to Round Two. And during this time, again, everyone\u2019s trying to cryptanalyze their own and everybody else\u2019s.<\/p>\n<p><strong>Host: Sure.<\/strong><\/p>\n<p>Brian LaMacchia: And to say what they can learn about it. And it\u2019s up to NIST to whittle it down, and we believe that then there will be a Round Three, and that again, in about five years or so, they will announce some small subset of algorithms that will be approved, some for public key encryptions, some for digital signatures.<\/p>\n<p><strong>Host: To be implemented as the standard.<\/strong><\/p>\n<p>Brian LaMacchia: As the standard. They will make what\u2019s called a FIPS, a Federal Information Processing Standard, which is an official US Government standard. And then, what, certainly we here at Microsoft, and others have encouraged us to do, is to then take that to an international standards organization such as ISO, and make it an international standard. Because we really want, whatever comes out of this process, that everyone around the world has contributed their intellectual horsepower to, and has analyzed, you know, as much as possible, to become an international standard. Because you need international standards for interoperability.<\/p>\n<p><strong>Host: Absolutely.<\/strong><\/p>\n<p>Brian LaMacchia: We want everyone to, basically, agree on strong, safe and secure algorithms. So, the US Government standardization is a step in that process, but it\u2019s not the end of it.<\/p>\n<p><strong>Host: And this is all aiming towards a post-quantum world.<\/strong><\/p>\n<p>Brian LaMacchia: That\u2019s right. This is all about getting algorithms in place so that, if and when cryptographically-relevant quantum computers become real, that we will have algorithms that we will already have transitioned to.<\/p>\n<p><strong>Host: So, let\u2019s talk about that timeline for a second. Realistically, I\u2019ve heard, from you and others, that 15 years maybe, optimistically, 15 years. But why the 15-year workback plan? Why are you working on this now when you\u2019ve got enough problems in a cloud-based world, and all the other things you\u2019ve referred to?<\/strong><\/p>\n<p>Brian LaMacchia: Well, so that actually is the number I started with 2015. And what happened is I went&#8230;<\/p>\n<p><strong>Host: Oh.<\/strong><\/p>\n<p>Brian LaMacchia: Yeah. I went to Krysta and her team, because we had started seeing these signals, and I said, okay, when do you all think that there\u2019s a reasonable chance that we\u2019ll have a cryptographically-relevant quantum computer? And at that time, they were saying about 15 years, which was 2030. So, I thought, okay, 2030 is a long time away. And then you start thinking about all the things that you have to do between now and 2030 to, effectively, upgrade the internet. Because that\u2019s really what you\u2019re talking about, right? You have to research new algorithms. You have to try to attack them. You\u2019ve got to start a standardization process. You\u2019ve got to prototype them. You\u2019ve got to do test deployments. You\u2019ve got to get them running on your own infrastructure. You\u2019ve got to upgrade all your customers using your software. And then you have to turn off and decommission the things that will be broken. And when I look at how long it took us, as an industry, to do that for the MD-5 hash function after Professor Wang\u2019s break, and I look at how long it took to do that with the SHA-1 hash function, you know, you add the pieces up, you need about 15 years. So, I didn\u2019t think we were actually starting too soon. I think we were starting kind of right on time, and I think we\u2019re still about right on time, if that 2030 number is still accurate. And it\u2019s good to see the progress that\u2019s being made within NIST. But I\u2019m still encouraging people to try to move a little bit quicker and to start taking our own prototypes and start deploying in test environments to see how flexible their software is to handle these types of algorithms. And you can do that today.<\/p>\n<p><strong>Host: So that leads us into the concept of cryptographic agility, which we referred to earlier.<\/strong><\/p>\n<p>Brian LaMacchia: Yes.<\/p>\n<p><strong>Host: Talk about what that is and why it\u2019s necessary.<\/strong><\/p>\n<p>Brian LaMacchia: Cryptographic agility, basically, is an architectural principle in your software, that where you use cryptography you do not hardcode in a dependency on one or a small number of algorithms. It\u2019s all about making it very easy to reconfigure your software to use something else, for a number of reasons. But everywhere that you have dependency on a cryptographic algorithm, you want to make sure that you can very easily reconfigure it if, all of a sudden, somebody steps up and tells you that they can break your hash function, you want to be able to quickly flip everything over to use another hash function. And if know that quantum computers are coming, and that we have to prepare for the post-quantum, world, we want to make sure that all of our software that currently uses public key cryptography is designing in the ability to use a quantum-resistant algorithm, even though we may not know exactly what that algorithm is yet.<\/p>\n<p><strong>Host: Or when they\u2019re going to need it.<\/strong><\/p>\n<p>Brian LaMacchia: Or when they\u2019re going to need it. But we can start making sure that all of our systems have that agility today. And part of the reason that my team doesn\u2019t just do the theoretical work, but we put out these high-performant, constant-time, side channel-resistant limitations is so that we can actually integrate them into the commonly-used security protocols today and show how those algorithms would work, and that\u2019s why you can actually go run the common algorithms like TLS or SSH or VPNs with our post-quantum algorithms in the mix.<\/p>\n<p><strong>Host: Talk about this concept of, \u201crecord now, break later,\u201d or as you\u2019ve phrased it, \u201crecord now, exploit later.\u201d Why should we be worried about somebody getting encrypted data that there\u2019s no way they can unencrypt right now?<\/strong><\/p>\n<p>Brian LaMacchia: So, this is a real worry. In fact, it\u2019s another reason why even without quantum computers existing today, you may want to deploy post-quantum right now. You have to assume that if you\u2019re sending sensitive data over a public network, that your adversary \u2013 whomever your adversary is \u2013 will record that data, has access to the public channel. That\u2019s why you\u2019re encrypting it in the first place. But data storage is cheap. Recording is cheap. So, if you and I are communicating over an encrypted connection, we have to assume that our mutual adversary is recording that traffic and storing it away for the day in the future when quantum computers are real, and the adversary can come back and use the quantum computer in the future to learn about what you and I talked about on the encrypted channel today. Now, if we\u2019re exchanging recipes or something that we don\u2019t think has a lot of long-term secret value, that may not matter.<\/p>\n<p><strong>Host: Well, mine do.<\/strong><\/p>\n<p>Brian LaMacchia: Okay, well mine don\u2019t, okay? But, you know. But, let\u2019s say that you are a Nation-State, and you\u2019re sending information that\u2019s classified. And those things typically have, I understand, a 30- or 50-year, or longer, time horizon, a security horizon. And it\u2019s not just national government-level data. Let\u2019s say that you\u2019re in the pharmaceutical industry and some of your research is going to have a 20- or 30-year security horizon, because that\u2019s the patent protection on the drug, or that you are in any industry where the information\u2019s got a long security horizon. If the time in which you need the information to be protected is longer than when we think quantum computers are going to show up, you have to assume that information\u2019s going to be recorded and broken when an attacker has access to a quantum computer. And so, your protection horizon is truncated by the appearance of quantum computers if you\u2019re only using classical algorithms. So, if you\u2019re trying to protect data for say fifty years today, you should be using a combination of the best classical schemes that we have right now, and a post-quantum scheme to try to give you some protection beyond the advent of quantum computers. That\u2019s the safest thing. It\u2019s what we call a hybrid scheme, where you use the best classical schemes that we have many, many decades of knowledge about from studying, and add in some new protection.<\/p>\n<p><strong>Host: Well, let\u2019s say that does scare me and I want to have that post-quantum algorithm or quantum-resistant algorithm. Can I get it?<\/strong><\/p>\n<p>Brian LaMacchia: Yeah, in fact, all of these submissions to NIST, as part of the submission, everybody had to make open source implementation available with their algorithms. In fact, your listeners can go out to GitHub, and they can go download all of our code, and you can go get those libraries today and start using them. And if you happen to be a customer of Open SSL, a very common TLS implantation, or Open SSH, or Open VPN, you can run that today. We even built a nice little demonstration device. We took a little raspberry pie and we turned it into a combination Wi-Fi hotspot and post-quantum VPN endpoint. So, I can take that with me anywhere in the world, and it sets up a VPN to a Linux machine running in Azure. That is my other endpoint. And I can connect wirelessly to the hotspot in my hotel room, and I\u2019ve got a post-quantum tunnel back to the Azure cloud.<\/p>\n<p><strong>Host: And all I\u2019ve got is a Starbucks open, unsecured network.<\/strong><\/p>\n<p>Brian LaMacchia: You probably want a little bit more than that.<\/p>\n<p><strong>Host: I probably do, but &#8211; yeah, I should hang out with you more. Speaking of the things that scare me.<\/strong><\/p>\n<p>Brian LaMacchia: Yes.<\/p>\n<p><strong>Host: You gave a talk recently that you subtly titled, How to Prepare for Certain Catastrophe. And that\u2019s a perfect setup for the question I ask all my guests, which is, is there anything that keeps you up at night?<\/strong><\/p>\n<p>Brian LaMacchia: Yeah, so the thing that keeps me up at night is that, say Krysta Svore and her team are going to be successful sooner rather than later. And by that, I mean that we\u2019re going to see quantum computers show up more quickly than we anticipate, that the qubit construction challenges and the scaling problems will get solved by the very smart people working on them faster than we can standardize and deploy defenses. There\u2019s this arms race going on between the quantum computing folks who are trying to build the quantum computers, and the post-quantum cryptographers trying to make sure the defenses are out there before the quantum computing people are successful. That\u2019s what keeps me up at night, but it\u2019s a good problem to have.<\/p>\n<p><strong>(music plays)<\/strong><\/p>\n<p><strong>Host: How did you wind up doing cryptography research? What was your path to MSR?<\/strong><\/p>\n<p>Brian LaMacchia: It started as an undergrad at MIT. I was a co-op student at AT&T Bell Labs. And during my junior year, I took an undergraduate class in cryptography from Professor Shafi Goldwasser, who is now a Turing Award-winner for her work with\u00a0Silvio Micali in cryptography. And cryptography is this weird area of computer science that is taking some of the purest mathematics and number theory and applying it to real-world practical privacy and security problems. And that was my jam. And, at the end of the class, I asked Shafi if she could recommend some people at Bell Labs who were doing cryptography for my next summer assignment. And I was fortunate enough that she pointed me to Andrew Odlyzko, who was\u2026 turned out to be my mentor for my master\u2019s thesis. And I did a couple summers and a master\u2019s thesis at Bell Labs, in breaking what were then called Knapsack Cryptosystems, which are no longer used, because we\u2019ve, pretty much, broken them completely. But they were a type of public key cryptosystem that was being studied at the time. And that led to graduate school. Actually, my PhD was in artificial intelligence, and I went back to Bell Labs because they were looking for computer scientists with an economic, legal or social bent to look at public policy computer science research. But the work I was doing was interesting to Microsoft, and I got recruited out into the product teams. And then got recruited into a group to become a cryptographic architect for some work we were doing on trusted computing very early on. And in 2005, I ended up over in corporate R and D, working on this little, what I call a security SWAT team, basically, for one of our former CTOs. And in 2009, we got reorganized into Microsoft Research into this new applied division, and that\u2019s still kind of where I am. And I have a mix of researchers and engineers, you know, developers, program managers on my team. And everything that we do is both about furthering the academic field as well as putting open source implementations of our algorithms and protocols out for everyone else to use.<\/p>\n<p><strong>Host: Right. Well, and that\u2019s a beautiful segue to&#8230; As we close, give some parting advice to researchers who are listening to this podcast, potential researchers\u2026 What might be on the horizon for them that you think would be good hard problems to work on, from your perspective, in this sort of math-intensive side of computer science research?<\/strong><\/p>\n<p>Brian LaMacchia: Well, here\u2019s the easy softball one. If there\u2019s people out there that want, that are interested in cryptanalysis, there\u2019s sixty targets, very easy targets, in the NIST competition, for people to go do cryptanalytic work. Because all of these algorithms are under consideration, and the more we know about something, the better. One of the reasons I would not recommend that we just solely move to only post-quantum algorithms today is that none of these algorithms have been studied as long as, say, RSA and elliptic curve-based things. So, that\u2019s why I actually think, for the first about decade of deployment, we\u2019re going to do hybrid schemes where we\u2019ll use both. That probably means you end up digitally signing things with two keys, one classical and one post-quantum. So, there\u2019s a lot of cryptanalytic work there. And I think we\u2019re still learning about leakage, ways in which our implementations on software and hardware leak information that makes it easy to break. You\u2019re not breaking the mathematics. You\u2019re effectively bypassing the mathematics by inferring bits of a secret key through physical properties of the device. And we have to use physical devices to work on this. And that\u2019s a very rich area. Another area that we\u2019re starting to do a little bit of work on, but I think holds a lot of promise, is in formally verified implementations. And I think that\u2019s a very rich area to doing work on within the cryptographic application space.<\/p>\n<p><strong>Host: So, there\u2019s a lot of, still, fruitful areas of exploration and research?<\/strong><\/p>\n<p>Brian LaMacchia: Oh, absolutely. My team did some work back in 2008 and 2009 on distributed key management. And that\u2019s for, how do you share secrets securely among, say, every machine and every rack in a datacenter, without having somebody plug a USB device into every machine manually? And there are some non-trivial problems in that space. Key management of cryptographic keys is a very important problem, and it doesn\u2019t tend to get much attention as it should, and I think that\u2019s another fruitful space.<\/p>\n<p><strong>Host: I have to ask you one more question.<\/strong><\/p>\n<p>Brian LaMacchia: Sure.<\/p>\n<p><strong>Host: How do you manage your passwords?<\/strong><\/p>\n<p>Brian LaMacchia: Perfectly fine question. I have a couple of, what I consider, very high-value passwords, which are all in my head. For all the typical website logins, I use a password manager, so that plugs into the browser. And then that is combined with a master password that unlocks that vault, and a physical device that I plug in. So, I do two-factor authentication, and everybody should.<\/p>\n<p><strong>(music plays)<\/strong><\/p>\n<p><strong>Host: Brian LaMacchia, thank you for talking to us today. It\u2019s been really, really interesting.<\/strong><\/p>\n<p>Brian LaMacchia: It\u2019s been my pleasure. Thank you very much for having me.<\/p>\n<p><strong>Host: To learn more about Dr. Brian LaMacchia, and how Microsoft is working to ensure online security and privacy in a post-quantum future, visit <a href=\"https:\/\/www.microsoft.com\/en-us\/research\/\">Microsoft.com\/research<\/a>.<\/strong><\/p>\n","protected":false},"excerpt":{"rendered":"<p>Episode 38, August 22, 2018 You know those people who work behind the scenes to make sure nothing bad happens to you, and if they\u2019re really good, you never know who they are because nothing bad happens to you? Well, meet one of those people. Dr. Brian LaMacchia is a Distinguished Engineer and he heads [&hellip;]<\/p>\n","protected":false},"author":37074,"featured_media":501959,"comment_status":"closed","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"msr-url-field":"https:\/\/player.blubrry.com\/id\/36405846\/","msr-podcast-episode":"","msrModifiedDate":"","msrModifiedDateEnabled":false,"ep_exclude_from_search":false,"_classifai_error":"","footnotes":""},"categories":[240054],"tags":[],"research-area":[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-501956","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-msr-podcast","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\/36405846\/","podcast_episode":"","msr_research_lab":[],"msr_impact_theme":[],"related-publications":[],"related-downloads":[],"related-videos":[],"related-academic-programs":[],"related-groups":[144840,381431],"related-projects":[428250,480492],"related-events":[],"related-researchers":[],"msr_type":"Post","featured_image_thumbnail":"<img width=\"960\" height=\"540\" src=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site.png\" class=\"img-object-cover\" alt=\"photo of Brian Lamaccia\" decoding=\"async\" loading=\"lazy\" srcset=\"https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site.png 1400w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-300x169.png 300w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-768x432.png 768w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-1024x576.png 1024w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-1066x600.png 1066w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-655x368.png 655w, https:\/\/www.microsoft.com\/en-us\/research\/uploads\/prod\/2018\/08\/maryattphotography-MS-Research_20180816_Brian-Lamaccia_1400x788_Site-343x193.png 343w\" sizes=\"(max-width: 960px) 100vw, 960px\" \/>","byline":"","formattedDate":"August 22, 2018","formattedExcerpt":"Episode 38, August 22, 2018 You know those people who work behind the scenes to make sure nothing bad happens to you, and if they\u2019re really good, you never know who they are because nothing bad happens to you? Well, meet one of those people.&hellip;","locale":{"slug":"en_us","name":"English","native":"","english":"English"},"_links":{"self":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/501956"}],"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\/37074"}],"replies":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/comments?post=501956"}],"version-history":[{"count":12,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/501956\/revisions"}],"predecessor-version":[{"id":626532,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/posts\/501956\/revisions\/626532"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media\/501959"}],"wp:attachment":[{"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/media?parent=501956"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/categories?post=501956"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/tags?post=501956"},{"taxonomy":"msr-research-area","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/research-area?post=501956"},{"taxonomy":"msr-region","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-region?post=501956"},{"taxonomy":"msr-event-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-event-type?post=501956"},{"taxonomy":"msr-locale","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-locale?post=501956"},{"taxonomy":"msr-post-option","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-post-option?post=501956"},{"taxonomy":"msr-impact-theme","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-impact-theme?post=501956"},{"taxonomy":"msr-promo-type","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-promo-type?post=501956"},{"taxonomy":"msr-podcast-series","embeddable":true,"href":"https:\/\/www.microsoft.com\/en-us\/research\/wp-json\/wp\/v2\/msr-podcast-series?post=501956"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}