Microsoft Research Blog

The Microsoft Research blog provides in-depth views and perspectives from our researchers, scientists and engineers, plus information about noteworthy events and conferences, scholarships, and fellowships designed for academic and scientific communities.

New England Researcher Finds Her Bliss

May 14, 2009 | By Microsoft blog editor

By Rob Knies, Managing Editor, Microsoft Research

Even now, almost a year after joining Microsoft Research New England, Yael Tauman Kalai can hardly believe her good fortune.

“Really, really awesome,” enthuses Kalai, 34, about her experience at the lab, based in Cambridge, Mass. “Frankly, it’s kind of too good to be true. I almost feel like I need to enjoy it because it can’t last. It’s too good to last, so I should enjoy every day I’m here.”

Jennifer Chayes, managing director of Microsoft Research New England, presumably has every intention of ensuring that such delight does continue to last—if only to maintain the stream of accolades applied to the lab by Kalai, one of Chayes’ key hires in getting the facility, which opened in July 2008, up and running.

Yael Tauman Kalai

Yael Tauman Kalai (Photo by Paul Oka)

“I really have time to do great research and have great people around me,” Kalai says. “The people in our lab are extremely smart. It is really fun to work with them.”

With cryptography as her primary research interest, Kalai found herself on a rather different career path a year ago. After obtaining her Ph.D. in Computer Science in 2006 at the Massachusetts Institute of Technology (MIT), she and her husband, Adam Kalai, now also of Microsoft Research New England, accepted jobs on the faculty at the Georgia Institute of Technology. They deferred their start by a year to work as post-doctoral researchers, splitting that time between Microsoft Research Redmond and the Weizmann Institute of Science, located in Rehovot in her home country of Israel.

“My husband and I were both in academia,” Kalai says, “so we had to solve the two-body problem. We went to Georgia Tech for tenure-track positions, and we were supposed to be there for the rest of our lives. That’s what we planned on.”

The couple embraced their new life: buying a house, beginning renovations.

“We took ourselves very seriously,” Kalai says. “We were planning to be there until the day we die.”

But the best-laid plans …

“About seven months later,” she recalls, “we got a phone call from Jennifer and Christian [Borgs, deputy managing director of Microsoft Research New England]. They were telling us that they were opening a new lab and asked if we’d like to join.”

Not long thereafter, the Kalais were headed toward Massachusetts. Why the switch? For Yael Kalai, it was all about the research.

Benefits of Academia

“Essentially,” she says, “this has all the benefits of academia, in the sense that we can do whatever research we’re interested in, really basic research.

“I do teach at MIT,” she adds, referring to the freedom the New England lab grants her, “so I like teaching, but I can choose what to teach, and I can choose not to teach. I don’t have to teach undergrad courses that I’m not interested in. I don’t need to apply for grants, and I get the opportunity to work with the best students. It’s really great.”

That self-understanding, however, didn’t come immediately. Only after reflection was Kalai able to discern that Microsoft Research might offer a good fit for her personal research needs.

“For me to do good research, there are several things I need,” she says. “One, the main thing, is time. I want to have time to think. It’s very important. Finding time to research is not easy.

“Here, I really have time. They take all the other stuff away from you and give you time to think, which is really nice.”

And then there’s the location.

“Our lab is very close to MIT and Harvard, and we have joint seminars,” Kalai says. “There’s a lot of activity and a lot of great people coming by, the best people in the field. There are so many people to work with. It’s really great.”

That academic environment also plays into her research interests, which are primarily in the realm of theory.

“Broadly speaking, it’s theoretical computer science,” Kalai says. “More specifically, most of my research is in cryptography: how to encrypt messages, how to sign digitally, how to do things securely, how to trade online in a secure manner.

“I hope to solve really significant problems in my field,” she adds. “I believe this will also be my goal 20 years from now, but of course, it may change.”

In particular, in her first year at Microsoft Research New England, Kalai has found time to complete three significant projects, two of them concerned with cryptographic schemes.

Secret Keys

“In cryptography,” she explains, “there is always a secret key involved. Typically, it is assumed that the secret key is totally secret and that no information about this key is leaked. Under this assumption, we can do many cryptographic tasks, such as secure encryption.

“But what if some information about the secret key is leaked? What if, somehow, information comes out about my secret key? Can I still do cryptography? If the entire secret key is leaked, then no, there’s nothing you can do. But what if not everything is leaked, if the secret key is still somewhat hidden?

“We show that, very loosely speaking, as long as not everything is revealed, you can still do cryptography. We had two projects along those lines, using different cryptographic schemes and solving different tasks, but both of them had to do with the possibility of the secret key being leaked.”

The third project Kalai has completed recently involves complexity theory and the generation of randomness.

“Randomness is essential for cryptography,” Kalai says. “It is known that many cryptographic tasks are impossible to do without randomness. The problem is that it is unclear how to get randomness in the real world. So the question that people asked is: Can we somehow generate randomness?”

“There has been a lot of work on this problem. In general, the answer is no. But a long line of research has focused on the following question: Let’s say we have a weak source of randomness. It’s not totally random, like heads/tails probability, but it still has some unpredictability in it. Can we extract randomness?

“Again, the answer is no. But what if we have several such weak sources, independent weak sources? Each one has a little bit of randomness. Now, can we extract? There has been a lot of work, first showing, yes, if you have many sources; then also yes, if you have fewer sources, and fewer, and fewer. Finally, it was shown that if you have two sources, you can, but the weak sources have to be not so weak. They need to be quite strong sources.

“What we showed,” Kalai concludes, “is that you can extract randomness from only two sources, even if those two sources are quite weak, but we needed to use some cryptographic assumptions.”

Obviously, this is not the kind of work undertaken by just anyone. It takes a special kind of mind to theorize on such levels. And when you narrow the pool of theory-minded researchers by gender, well, let’s just say that Kalai is something of a rarity.

“There are very few women in cryptography,” she stipulates. “Very, very few. But that is another thing that is really awesome about this place. In many places, being a woman in computer science is a real issue.

‘Very Comfortable’

“Here … I don’t know if it’s because Jennifer, the head of the lab, is a woman. I’m not sure what it is. But I told Adam the other day, ‘Wow, I haven’t thought about the fact that I’m a woman in the field for a long, long time—almost a year.’ It didn’t even occur to me. It just doesn’t come up. It’s very comfortable to be a woman in this lab.”

In fact, so comfortable has Kalai found the environment at Microsoft Research New England that she has forged a new relationship with MIT, inaugurating the MIT Cryptography Seminar Series, a joint effort with the New England lab.

“When I was a student here at MIT,” Kalai recalls, “We had a cryptography seminar every Friday. It has been going on for many years. And when I came here, I wanted to do some seminars, and I asked if they wanted to do one with us, rather than having two.”

A deal was reached, in which the two institutions would conduct a seminar every other week, in alternating locations. And it benefits both sides.

“It has been very successful,” Kalai says. “We have great speakers.”

It’s all about surrounding yourself with the best people. That’s what you get when you establish yourself in one of the most stimulating academic environments the world has ever seen.

“I want to do great research and advance the state of the art,” Kalai states. “To do that, my goal is to have great post-docs, the best research people available to come here. The best researchers are often in academia. Wherever they are, I want to collaborate with them. I want them to come here. I want us to work with them.”

And, she makes it clear, Microsoft Research New England has established itself as an integral player in that community.

“Having close ties with MIT is just one way of doing that,” she says. “Having a crypto seminar enables us to invite the best crypto people to come here, spend a few days or a week here. We get a chance to work with them, get a relationship with them. By having that, then we get great interns, great post-docs. It feeds itself. Once great people come here, they tell other people, and very, very quickly, you establish a great name. Everybody all of a sudden wants to visit you, and it becomes a really world-class place to do research.”

Hectic Life

Moving from academia into a new job at a brand-new facility, relocating from Georgia to New England, pursuing stupefyingly challenging research on a world-class level—that’s enough to keep anybody busy, right?

Well, for Kalai, there is one more thing—two actually. Their names are Yo-Yo, 3, and Maya, 1—or, as Kalai calls them, “our two little cuties.”

How do Kalai and her husband manage?

“I took out anything unnecessary in my life,” she says, “anything that is not important for our health, wellbeing, our kids, or our jobs. I didn’t give up things that are very important to me, such as doing yoga. I still go to the gym at least twice, three times a week. I have my kids, I have my work and Adam, and I do yoga. That is more or less it. I don’t have time for anything else.”

It helps, of course, that the family has domestic assistance. More important is the quality of the familial interactions.

“I find very effective ways to be with the kids,” Kalai says. “I take my son to a café with me at least once a week. We spend one hour, just the two of us; we go on a date. And he knows it’s a date with me. It’s a short amount of time, but it’s very, very special to us.

“I feel like I’m spending time with my kids. I could spend more, but I feel like I’m very happy with the relationship we have. This is our life, and I think we’re very happy with it.”

And the same, it appears, applies to work.

“I could spend more time working had I had no kids,” Kalai says, “but it was my choice to have kids, and I feel like I’m quite effective at work. People know if they want to talk to me, it has to be related to work. They’ve stopped inviting me for all these breaks, because every time, I say no.”

One year on, Yael Kalai counts this grand experiment a rousing success.

“Yes,” she says, “I’m quite satisfied with how things are going.”

Up Next

Josh Benaloh

Security, privacy, and cryptography

Securing the vote with Dr. Josh Benaloh

Episode 65, February 27, 2019 - Dr. Josh Benaloh gives us a brief but fascinating history of elections, explains how the trade-offs among privacy, security and verifiability make the relatively easy math of elections such a hard problem for the internet, and tells the story of how the University of Michigan fight song forced the cancellation of an internet voting pilot.

Microsoft blog editor

Artificial intelligence, Ecology and environment, Human-computer interaction, Security, privacy, and cryptography

Internships Ahoy! with Kirsten Bray, Wei Dai and Sara Beery

Episode 42, September 19, 2018 - On today’s podcast, you’ll hear the stories of three of these interns, each of whom came to Microsoft Research from a different field, with a different story and a different perspective, but all of whom share MSR’s passion for finding innovative solutions to the world’s toughest challenges.

Microsoft blog editor

Algorithms, Artificial intelligence, Mathematics, Security, privacy, and cryptography

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

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

Microsoft blog editor