Tales from the Crypt(ography) Lab with Dr. Kristin Lauter

Published

Dr. Kristin Lauter – Principal Researcher, Research Manager. Photo courtesy of Maryatt Photography.

Episode 19, 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.

Related:

Transcript

Kristin Lauter: 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.

(Music plays)

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

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 Researcher Manager for the Cryptography Group at Microsoft Research, can. And she’s 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. That and much more on this episode of the Microsoft Research Podcast.

(Music plays)

Host: Kristin Lauter, welcome to the podcast today. It’s great to have you with us.

Kristin Lauter: Thank you so much. Nice to be here.

Host: 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.

Kristin Lauter: 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 my Microsoft and apply the mathematics that I had learned in graduate school and worked on as an assistant professor at the University of Michigan to work in the exciting area of cryptography.

Host: So, tell us a little bit more about the general field of cryptography. We’ve got mostly high-tech listeners who are probably 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?

Kristin Lauter: 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.

Host: So, it’s all about being able to share information and not have somebody that shouldn’t have that information get it.

Kristin Lauter: 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, 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.

Host: 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?

Kristin Lauter: Well, I was very excited when I came to Microsoft to work on elliptic 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 5 years here on kind of evangelizing the technology and working with another researching 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 entrée for me into the industry, because I got to learn, through interacting with product groups, 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. So, it was really fun.

Host: Can you take a minute to explain it to our audience?

Kristin Lauter: 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.

Host: Now I understand it just slightly better than I did before. One of the other things you’re known for is your work in supersingular isogeny graphs. Tell us the story about how you came to introduce it as a hard problem in cryptography.

Kristin Lauter: Well, that was a really lucky and great coincidence. With some collaborators, a post-doc 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 supersingular 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 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 crypto systems 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 come up with polynomial-time quantum algorithms yet, it’s under serious consideration for standardization as a post-quantum technology.

(Music plays)

Host: 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?

Kristin Lauter: So, homomorphic encryption allows to compute on encrypted 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 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 cipher texts. And that allows us to actually operate on them. As mathematicians, we can think of cipher texts as just being these mathematical objects, and we can do operations that correspond to circuits, which is how computers, you know, 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.

Host: 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?

Kristin Lauter: Well, the AI world that we’re living in, we’re collecting more and 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.

Host: So, you’re able to compute and operate on encrypted data?

Kristin Lauter: 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 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.

Host: That just seems wild to me, even trying to wrap my brain around how that can happen. I’m impressed by you people. That’s incredible.

Kristin Lauter: Well, that’s the reaction that we get from a lot of customers and potential partners that we talk to, that its 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.

Host: It is. It’s a beautiful thing. Let’s drill in on a couple of homomorphic stories, as you called them the other day. Um… These must be the kinds of stories mathematicians tell their kids at bedtime. You framed one of the stories about healthcare and genomic privacy, and you called it one of the most motivating things in your whole career. So, tell us about that.

Kristin Lauter: 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 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.

Host: Right. So, tell me the story about iDASH, and how that all played out with this homomorphic encryption.

Kristin Lauter: 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 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 had 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 them come together in a workshop to share each others’ solutions. And the powerful thing about this model for 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 time frame, and to produce results which can provide benchmarks that show how possible certain tasks are with homomorphic encryption today.

Host: I love that. In fact, my brain is just going 1,000 directions right now. Everything you say gives me another question in my mind. How else is this playing out, the homomorphic encryption? Does it have other applications that you think would be interesting research threads for people?

Kristin Lauter: 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, mathematicians, computer scientists, working with machine-learning researchers, biostatisticians, even medical practitioners and engineers, and policymakers to bring this all together to provide solutions. So that’s a very exciting area to be working in now.

(Music plays)

Host: 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?

Kristin Lauter: Yes, and I’m still working towards that vision, and 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. 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. So, I’m still working toward that vision. I believe in it. I believe we’re going to get there.

Host: What are your biggest challenges to getting there?

Kristin Lauter: Well, homomorphic encryption is a relatively new technology in the sense that it’s only 10 years old. So that might sound like 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, and to standardize the technologies. So, we’re just getting to that point now where, kind of, almost 10 years after the first solutions were introduced, we’ve put together 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.

Host: That’s really important, getting the standards in place and then moving forward as a group rather than just a bunch of individual agents that…

Kristin Lauter: That’s right. And it also helps to build the public trust in the technology.

Host: 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 work on in terms of standardizing and getting a lid on it?

Kristin Lauter: 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 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 their security will be in the future at least, say 10, 15 years into the future.

Host: Right, 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.

Kristin Lauter: 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. 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.

Host: And I imagine that there’s a lot of new applications, career-wise, for mathematics now even than there were 10 years ago, given what’s going on in the high-tech world.

Kristin Lauter: 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.

Host: Yeah. In fact, even as I think about it, I’m not 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.

Kristin Lauter: 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. It was 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, 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, more – these are fun areas that students love to learn. They’re very motivating for students.

(Music plays)

Host: Tell us about your involvement as a fellow in the Association for Women in Mathematics and your work as a cofounder in Women in Numbers Network.

Kristin Lauter: 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. What we did was to bring together all of the, kind of, leading women that we knew in number theory and asked them to kind of work together with us to design research projects that students and post docs could come and work on, collaboratively at a conference. So that was our first conference in 2008 called the WIN Conference. And we’ve 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 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.

Host: 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?

Kristin Lauter: 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 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 percent 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 percent. That’s the number you’re shooting for. Get to 30 percent female faculty, and from there, you can get to 50 percent.” 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 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, 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 WIN, so they don’t have as 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 and math.

Host: Is this international, or is it in the United States, or how does it spread globally?

Kristin Lauter: It is international. For example, for WIN, we have a whole ‘nother series of conferences called WINE, which is Women in Numbers in Europe. And I particularly like that acronym, WINE.

Host: I’m going. I’m not even in numbers, but I like wine.

Kristin Lauter: 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 that also help to organize them.

Host: So, Kristin, Grace Hopper is a conference that’s for women in technology. How is it impacting 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?

Kristin Lauter: 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 and show that there are great career paths where they can really make a difference and have an impact in the world.

Host: So, maybe it’ll be the Kristin Lauter Conference for Women in Mathematics.

Kristin Lauter: 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.

Host: 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?

Kristin Lauter: 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 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.

Host: 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?

Kristin Lauter: I would say I think it’s a very rewarding career. And coming to Microsoft Research as, for example, 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.

Host: Yeah, yeah. So, it’s obvious what gets you up in the morning. Ummm… 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.

Kristin Lauter: Nothing really keeps me up at night. But…

Host: I keep other people up at night…

Kristin Lauter: 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. 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.

(Music plays)

Host: That’s a good problem to solve. Kristin Lauter, thank you so much for sharing your passion with us, and taking time out of your schedule to come be on the podcast today.

Kristin Lauter: Thank you. It was a great pleasure talking with you.

(Music plays)

Host: To learn more about Dr. Kristin Lauter, and the not-so-secret world of computer cryptography, visit Microsoft.com/research

Related publications

Continue reading

See all podcasts

Research Areas

Related labs