Microsoft Research Podcast - 019 - Tales from the Crypt(ography) Lab with Dr. Kristin Lauter

Episode Date: April 11, 2018

From ancient hieroglyphics to secret decoder rings to World War II Enigma code-makers and code-breakers, cryptography has always held a particular fascination for us. But few of us have the skills –... or can actually do the math – to unlock the mysteries of encrypted data. Fortunately, Dr. Kristin Lauter, distinguished mathematician, founder of the Women in Numbers Network, and Principal Researcher and Research Manager for the Cryptography Group at Microsoft Research, can. And she is using her powers for good, not for evil! Today, Dr. Lauter tells us why she feels lucky  to do math for a living, explains the singular beauty of elliptic curves and the singular difficulty of supersingular isogeny graphs, talks about how homomorphic encryption – part of the field of Private AI – allows us to operate on, while still protecting, our most sensitive data, and shares her dream of one day, seeing a Grace Hopper-like conference to celebrate women in mathematics.

Transcript
Discussion (0)
Starting point is 00:00:00 As mathematicians, our approach is to think hard about the problems we're trying to solve and figure out the best algorithms that we know for solving them. So if I wasn't before, then I firmly became an algorithmic number theorist when I came into cryptography. 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 Huizenga. From ancient hieroglyphics to secret decoder rings to World War II enigma code makers and code breakers,
Starting point is 00:00:38 cryptography has always held a particular fascination for us. But few of us have the skills, or can actually do the math, to unlock the mysteries of encrypted data. Fortunately, Dr. Kristen Lauder, distinguished mathematician, founder of the Women in Numbers Network, and principal researcher and research manager for the cryptography group at Microsoft Research, can. And she's using her powers for good, not for evil.
Starting point is 00:01:07 Today, Dr. Lauder tells us why she feels lucky to do math for a living, explains the singular beauty of elliptic curves and the singular difficulty of super-singular isogeny graphs, talks about how homomorphic encryption, part of the field of private AI, allows us to operate on, while still protecting our most sensitive data, and shares her dream of one day seeing a Grace Hopper-like conference to celebrate women in mathematics. That and much more on this episode of the Microsoft Research Podcast.
Starting point is 00:01:49 Kristen Lauder, welcome to the podcast today. It's great to have you with us. Thank you so much. Nice to be here. So you're a principal researcher and the research manager for the cryptography group at Microsoft Research, where you apply number theory and algebraic geometry to cryptography. That's right. Well, I'm one of the lucky ones to have such a great job to be able to spend my life researching the things that I love. So I was very lucky to find the opportunity to come to Microsoft and apply the mathematics that I learned in graduate school and worked on as an assistant professor at the University of Michigan to work in the exciting area of cryptography. So tell us a little bit more about the general field of cryptography. We've got mostly high-tech listeners who are probably
Starting point is 00:02:32 familiar a bit, but I think there's room for a little bit of an overview of the field. What is cryptography about and why is it important? So cryptography is essential in today's economy for securing our e-commerce and our cloud and all of our online presence and interactions. So the tools that cryptography provides are for encryption, which provides confidentiality for data while it's being stored or transmitted, but also authentication so that you know when you're interacting with a party online that they're actually the party that they say that they are. So you're actually buying something from the vendor that you think you're buying from rather than from somebody else. So there's a whole infrastructure around cryptography that we use in industry and government that's very important for securing our interactions. So it's all about being able to share information and not have somebody that
Starting point is 00:03:26 shouldn't have that information get it. That's right. So public key cryptography is the science of interacting publicly and ending up with something that's secret. So the exciting thing for me is that number theory is basically the foundation for public key cryptography. So the way public key cryptography works is that there's hard number theory problems that are used as the basis of security for these public key interactions. So that includes key exchange, encryption, digital signatures. So let's talk about your specific work right now. And you're known for several things in the field. And one of them is elliptic curve cryptography. So what is it? Why is it important? And how has it impacted the field? Well, I was very excited when I came to Microsoft to work on elliptic
Starting point is 00:04:16 curve cryptography. It had been proposed around 1985, but it was not yet being used widespread in the industry in 1999 when I came to Microsoft. And I worked for my first about five years here on kind of evangelizing the technology and working with another researcher in my team, Peter Montgomery, to develop our elliptic curve cryptography code and to optimize things and to make it work for different platforms. And that was a very exciting entree for me into the industry because I got to learn through interacting with product groups of what was really needed and how things work. And I got to work on real world problems that had a very real mathematical bent. So I got to go to the office of top executives and have them freak out when they found out they were having a meeting on elliptic curve cryptography. And I got to, you know, file patents where I was explaining elliptic curve technology to lawyers who were listening intently and trying to understand.
Starting point is 00:05:18 So it was really fun. Can you take a minute to explain it to our audience? Sure. So elliptic curves are a very beautiful object which have been studied in mathematics for more than 100 years. They're actually a curve, so they have a geometric aspect to them. They have a shape in some sense. But they also have a group structure, an algebraic structure, that allows you to take two points on the curve and add them together. And it's this group structure that you need and use in cryptography to create these public-key crypto systems. Now I understand it just slightly better than I did before. One of the other things you're known for is your work in super singular isogeny graphs. Tell us the story about how you came to
Starting point is 00:06:01 introduce it as a hard problem in cryptography. Well, that was a really lucky and great coincidence with some collaborators, a postdoc and a visiting researcher that were here at Microsoft Research with me. We were working on even a more complicated object, a higher dimensional version of supersingular isogeny graphs. And this was in 2005 when there was a lot of hype around the NIST hash function competition. So MD5 had been broken and it was clear that there was going to be a new hash function selected. And so there were a lot of ideas kind of swirling in the air. And we were working on these objects and realized, wow, walking around on super singular isogeny graphs could potentially be a really hard problem. And just because it was new, and that's what we do, we're mathematicians, we think about
Starting point is 00:06:48 cryptographic problems and how hard they are, proposing new ones, attacking current ones, improving algorithms. We thought, oh, well, since we can't figure out any way to break it, why don't we propose this as a hard problem? And we proposed a hash function to go along with it and presented it at the NIST hash function competition. So it was really fun to find out just a few years ago that interest in this proposal has resurfaced because of the current post-quantum cryptography competition, where we need all kinds of new ideas from mathematics to create new cryptosystems for which we don't currently know polynomial-time quantum algorithms. And since this was a new system that we had proposed, and no one has
Starting point is 00:07:31 come up with polynomial-time quantum algorithms yet, it's under serious consideration for standardization as a post-quantum technology. So let's talk a little bit about what I think is like the most interesting thing in your career right now, and that's homomorphic encryption. It's a pretty big deal for a lot of reasons. Tell us what it is, what's different about it, and why it's important in an AI world. So homomorphic encryption allows us to compute unencrypted data. So this is a very important breakthrough. Standardized crypto today that's in widespread use, such as block ciphers like AES or other types of ciphers like stream ciphers. If you take two encrypted texts and kind of try
Starting point is 00:08:27 to operate on them, add them together, or do something with them, you'll get just gibberish. So homomorphic encryption preserves the mathematical structure underlying the ciphertexts, and that allows us to actually operate on them. As mathematicians, we can think of ciphertext as just being these mathematical objects, and we can do operations that correspond to circuits, which is how computers compute on information. And we can make it so that you can do things like machine learning algorithms, doing predictions and training models and doing all kinds of exciting things to allow what we call private AI. Unpack that a bit more. Private AI is an interesting term, and I think it's super important in an AI world and the largeness of what we're doing with machine learning. How does that private AI come into play? Well, the AI world that we're living in, we're collecting more and
Starting point is 00:09:26 more data and we're improving our ability and our algorithms for processing that data. But as we do that, we're putting our privacy at risk in the sense that there could be very sensitive data being collected, for example, our health information, genomic information, financial information. Private AI is a set of tools which can be used to handle data in a private way and yet still provide AI services on top of it. So you're able to compute and operate on encrypted data. That's exactly right. So for example, for the first time, we can collect encrypted information from a customer and they may want to learn from that data in some way, get some business intelligence or get some prediction. And what we can do with homomorphic
Starting point is 00:10:18 encryption is we can handle those computations in encrypted form. So the client or the customer can encrypt their data and keep their key and never share their key with us, but share the encrypted data with us and ask for some prediction. And then we can give them this prediction by operating on their encrypted data. And what we're doing is we're giving them an encrypted prediction. So we don't learn their data or their prediction, and then we return it to them and they can use their key to decrypt it. So the information is never decrypted while we have access to it. That just seems wild to me. Even trying to wrap my brain around how that could happen,
Starting point is 00:10:55 I'm impressed by you people. It's incredible. Well, that's the reaction that we get from a lot of customers and potential partners that we talk to, that it's somehow a magic box. But from a mathematical perspective, it's very natural. What you've done is you've put the information into a structured mathematical form, and then you're operating on it. And as long as you do it in a way that preserves that structure of that data to begin with, as you operate on it, you continue to preserve that structure. And it's just mathematics. And that's the beauty of mathematics. It is. It's a beautiful thing. Let's drill in on a couple of homomorphic stories, as you called them the other day. These must be the kind of stories mathematicians tell their kids at bedtime. You framed one of the stories about health care and genomic privacy, and you called it one of the most motivating things in your whole career.
Starting point is 00:11:46 So tell us about that. Well, another lucky coincidence in my career was that as we started to make homomorphic encryption more practical, there was a genomics researcher here at Microsoft Research, David Heckerman, that said, hey, I bet you can do genomic predictions using your technology. And so we worked together with him and his group to show doing live genomic predictions using homomorphic encryption. And based on that, I started getting invited to a whole series of meetings that I would never have gone to otherwise. Biological data science at Cold Spring Harbor, for example, where I met the IDASH organizers
Starting point is 00:12:22 who are funded by NIH to run the Secure Genome Analysis Contest. So I got involved in a whole community of people in bioinformatics and biostatistics that are interested in protecting genomic data for patients for the future. And this is something that I found just really inspiring to be working on something such as health and genomic privacy, which I feel is so important for society and for which we have mathematical tools that can be helpful. Right. So tell me this story about IDASH and how that all played out with this homomorphic encryption? So when I first met the IDASH organizers, it was at the Cold Spring Harbor meeting, and I was doing a tutorial on homomorphic encryption and talking about some of the sample tasks we'd been able to show were possible with our practical homomorphic encryption techniques. And those included edit distance and chi-squared statistics. And so when they ran their secure genome analysis contest the first
Starting point is 00:13:26 year, they picked those as some of the tasks. And we actually won the edit distance track of that competition. And I used to joke that it was really funny because we had an unfair advantage since they picked a task we'd already been working on. But we developed a really great relationship with the IDASH organizers and the rest of the community. It's an international community of teams from industry and academia who work to solve these challenges each year and then come together in a workshop to share each other's solutions. advancing the state of the art is that, okay, we call it a competition, but that's a little bit beside the point. The point is really to work collaboratively on these challenges in a fixed timeframe and to produce results which can provide benchmarks that show how possible certain tasks are with homomorphic encryption today. I love that. In fact, my brain is just going a thousand directions right now. Everything you say gives me another question in my mind. How else is this playing out,
Starting point is 00:14:30 the homomorphic encryption? Does it have other applications that you could think would be interesting research threads for people? Absolutely. So I like to say when I talk about genomic privacy, that it's an area where we absolutely need that interdisciplinary work to make progress. So we're working together. We're mathematicians, computer scientists, working with machine learning researchers, biostatisticians, even medical practitioners and engineers and policymakers to bring this all together to provide solutions.
Starting point is 00:15:04 So that's a very exciting area to be working in now. So you said in a talk several years ago, my vision of the future, I'm quoting you, my vision of the future is that all data would be stored in the cloud in encrypted form. And then you kind of laughed and admitted that there were some problems with cryptographic cloud storage. So where are we now? Fast forward several years. Do you remember saying that? Yes, and I'm still working towards that vision. I still believe in it. So I believe that, well, first of all, we already know today that encryption is a very important technology for protecting people's data. And we like to say that you can protect data in transit, at rest, and while you're trying to compute on it.
Starting point is 00:15:55 And the standardized cryptography that we use today can help you protect the data while it's being stored. And what homomorphic encryption can do is to help you protect it in encrypted form, but still retain the utility of the data and be able to compute on it. Right. So I'm still working toward that vision. I believe in it. I believe we're going to get there. What are your biggest challenges to getting there? Well, homomorphic encryption is a relatively new technology in the sense that it's only 10 years old. So that might sound like
Starting point is 00:16:26 it's in the Stone Age when we think of how fast technology evolves these days. But typically for public-key crypto systems over the last 40, 50 years, there have been roughly at least a 10-year time lag before crypto technologies get adopted. And that's because the community needs to have time to think about how hard these problems are and to set the security levels appropriately. Right. a broad coalition of researchers in industry, government, and academia to come together to try to standardize this technology. And we're having our second workshop in March at MIT, where we're going to try to get broad approval for our standard document, which recommends security parameters. So that's the first challenge, is getting everyone to agree on what is the strength of these systems, kind of essentially how hard are these mathematical problems underneath. And then we plan to continue to build on that with this community to get agreement on a common set of APIs, for example, for how we can deploy this technology in the industry and have systems be interoperable and to work on a rich set of applications with the applications community. That's really important, getting the standards in place and then moving forward as a
Starting point is 00:17:51 group rather than just a bunch of individual agents. That's right. And it also helps to build the public trust in the technology. Yeah. And that brings up a question in my mind, with the exponential growth of technological devices and abilities, do new things sort of show up on your doorstep in the encryption world and you say, oh, got to think of that? I mean, how much does the onward push of technology impact what you're trying to work on in terms of standardizing and getting a lid on it? So there's always kind of new events that come in that can be disruptive. But as mathematicians, our approach is to think hard about the problems we're trying to solve and figure out the best
Starting point is 00:18:38 algorithms that we know for solving them. So if I wasn't before, then I firmly became an algorithmic number theorist when I came into cryptography. And what we do is we try to estimate the running time for the algorithms that will break the crypto systems we're proposing. And then we see, for example, how these algorithms evolve over time, how much we can improve them in different ways. And we estimate the running times for the future security of these systems. And so even though there can be disruptive events that come in, when we have a community of mathematicians working on these problems over time, we think we understand relatively well what
Starting point is 00:19:18 their security will be in the future, at least, say, 10, 15 years into the future. Beyond that, who knows? So you're a mathematician first, and you've got an amazing CV and are truly an inspiration. In fact, I've actually been told you have fans. Like, people find out you're going to be someplace and they say, I'm going to that. So talk about how you caught the math bug and how it's affected your own life. Well, I loved math from a very early age. So I used to do math problems in the car with my dad when I was young. So story problems. And I just loved it.
Starting point is 00:19:54 And I guess it was always very clear to me that that was something that was fun and that I was apparently good at. So I was allowed to work ahead in school on my own, and I just kind of zoomed through the curriculum. And I graduated from high school when I was 15, and I went to the University of Chicago. So I was very lucky to get into their undergraduate program and then to be encouraged to go to graduate school there. So as a career, I have found that it has much more importance and applications than what people realize. The mathematical community is, people sometimes don't realize that their kids can go into math and have a fabulous career in industry and in all kinds of areas. And so I try to spread that message as well. And I imagine that there's a lot of new applications career-wise for mathematics now,
Starting point is 00:20:48 even than there were 10 years ago, given what's going on in the high-tech world. Yeah. So there's a lot of areas where kind of math is underappreciated because it's not called by that name. For example, machine learning. Machine learning is the foundation of AI. Machine learning is just mathematics, but it's mostly computer scientists that are doing it these days. And so I'm in an interesting position being a mathematician working in the computer science research lab because I have access to great researchers on both sides. And it's really fun to see, but it can sometimes be frustrating to see the lack of communication or crossover between the fields. Yeah. In fact, even as I think about it, I'm not
Starting point is 00:21:31 sure how big the overlap is between computer science and math, because you'd think if you go into computer science, it's heavily mathematics-based. But if you're a mathematician, you're not necessarily a computer scientist. Absolutely. And even as an undergraduate at the University of Chicago, I was struck by the fact that some of the interesting mathematics was actually being picked up and taught in the computer science department because they realized even at that time, which was many years ago now, in the 80s, that this mathematics was very important as the foundation for things like cryptography, which computer science students study. And so they were teaching this interesting mathematics in the computer science department, which was frustrating to me because I said, hey,
Starting point is 00:22:13 we should be teaching this to undergraduates in math departments. And I still feel that way. I still feel we should be doing more cryptography in math departments. We should be doing more machine learning. These are fun areas that students love to learn. They're very motivating for students. Tell us about your involvement as a fellow in the Association for Women in Mathematics and your work as a co-founder in Women in Numbers Network. Well, I will not lie to you. There's still a lot of challenges for women to face in science, in our society, and in particular in mathematics and computer science. And I found that creating the Women in Numbers Network, which is a research network for women in number theory, gave me a huge boost in my career.
Starting point is 00:23:06 What we did was to bring together all of the kind of leading women that we knew in number theory and ask them to kind of work together with us to design research projects that students and postdocs could come and work on collaboratively at a conference. So that was our first conference in 2008 called the WIN Conference. And we built on it from there in 2008 called the WIN Conference. And we built on it from there to build up the WIN Network. And the WIN Network consists of now more than 200 women in number theory. And we have regular conferences. We publish volumes of research papers. So we've published around 50 research papers in number theory, each paper written by
Starting point is 00:23:43 a group of women number theorists, anywhere from four to seven number theorists. And this has been a really fun environment to get involved in because as the young women come into this network and see that they can contribute and that they're valued, they get inspired and they start to help lead the effort and organize the conferences. And so we now have kind of a whole generation of women in WIN that work together to support each other and do research together and have fun together. So how is that then reaching out to, say, the next generation of women in mathematics or number theory or computer science? Do you have any evangelical efforts for your organization? Absolutely. So what happened for me is that when I saw the excitement that this model generated, we call it the WIN model, I thought, this is too good to be true. We need to spread this model to
Starting point is 00:24:38 other areas of mathematics. Because for decades, we've had pipeline issues and kind of the leaky pipeline issue of women leaving the profession at different stages. And so we still have somewhere between 5% to 10% women faculty at the top research universities. And that's a number that is way too low. When I visit math departments today, I like to say 30%. That's the number you're shooting for. Get to 30% female faculty. And from there, you can get to 50%. Because Because of course, we should be at 50-50. And we find that when we have more women faculty, that that encourages more women students as well. But
Starting point is 00:25:15 the WIN model was obviously a powerful tool for advancing this vision. And so what I did was I decided to get involved in the AWM, the Association for Women in Mathematics, which is an almost 50-year-old professional society. Wow. With somewhere around 5,000 members and to try to bring this idea and this model into the AWM. And I became president of the organization. And during that time, we got an NSF grant for $750,000 to spread this model to the other areas. And now we're in year three of the grant. And so far, we've created almost 20 research networks for women in mathematics. So the other networks are not as old as Wynn, so they don't have as
Starting point is 00:26:01 many researchers. But each of those networks probably has at least around 50 women researchers in their area. So that represents a huge boost for women in research in math. Is this international, or is it in the United States, or how does it spread globally? It is international. For example, for WIN, we have a whole other series of conferences called WINE, which is Women in Numbers in Europe. And I particularly like that acronym, WINE. I'm going. I'm not even in numbers, but I like WINE. It's fun. And so there's a series of WIN conferences in Europe. But in each of these networks, for example, Women in Topology is co-organized by a woman in Europe. There's a number of people from around the world that both attend and take part in these research conferences and also help to organize them. So, Kristen, Grace Hopper is a conference that's for women in technology. How is it impacting
Starting point is 00:26:56 the field for women in general? And what else can you tell us about what we might be thinking for the future of women in technology? What I really like about Grace Hopper is it helps to celebrate the achievements of women in computer science. It helps to generate excitement and confidence for younger women in the field. And it serves as a recruiting platform for high tech to attract the top talent in computer science. So what I really wish is that we had a Grace Hopper Conference for Women in Mathematics as well. And so hopefully we'll get there. But that pipeline is so important that at the undergraduate level, we've got so much talent in young women going into science, and we just need to support them and motivate them to continue in the field
Starting point is 00:27:46 and show that there are great career paths where they can really make a difference and have an impact in the world. So maybe it'll be the Kristen Lauder Conference for Women in Mathematics. I don't know about that, but I think that Grace Hopper is a great achievement, and I hope that we can spread that model to other fields. I love this so much. So much. So tell me what brought you to Microsoft Research, and why might others in your field want to come here? When I first came to Microsoft, I couldn't believe how great the research environment was. Everybody had their doors open, and people actually cared about what I
Starting point is 00:28:25 worked on. So when I had my first meeting where I had to explain elliptic curve cryptography to lawyers and they had a video camera set up and they were videotaping me, I said, I've got to have it. This is what I want to do. But I also really like the interdisciplinary nature of it. Clearly coming from a math background and working with computer scientists was very exciting. But also the opportunity to have a real world impact. So to talk to our product teams, to talk to customers, to learn what their problems are and how we can help solve them has been a really exciting and rewarding aspect of my career here. What would you say to aspiring researchers, especially to women, who might want to get into this field and take up the research baton and run with it? I would say I think it's a very rewarding career. And coming to Microsoft Research as, for example,
Starting point is 00:29:19 an intern or a visitor is a great way to kind of get your foot in the door and test the waters. You can see if you like the kind of fast-paced collaborative environment. And my experience is that most interns that come to my group in the summer, the answer is yes, they love it. They're more productive than when they're just working by themselves. And they're inspired by the challenging problems and seeing all the great people around them doing great research. Yeah, yeah. So it's obvious what gets you up in the morning. Is there anything that keeps you up at night in your field? Because I mean, there's a lot of things to keep us up at night. Nothing really keeps me up at night. I keep other people up at night. I would say that I'm particularly motivated to help make change for women in society and in science. I think that there's a great place for women to help us solve our challenges in science.
Starting point is 00:30:17 And I'm particularly disturbed by the low numbers that we still see for women in scientific careers. So that's the problem I'd like to solve. That's a good problem to solve. Kristen Lauder, thank you so much for sharing your passion with us and taking time out of your schedule to come be on the podcast today. Thank you. It's a great pleasure talking with you. To learn more about Dr. Kristen Lauder and the not-so-secret world of computer cryptography,
Starting point is 00:30:50 visit microsoft.com slash research.

There aren't comments yet for this episode. Click on any sentence in the transcript to leave a comment.