Dr. Boyle Explores Secure Computation

Dr. Elette Boyle joined NTT Research as a Senior Scientist in the Cryptography and Information Security (CIS) Lab in October 2021. She has most recently been serving as Associate Professor of Computer Science at the Efi Arazi School of Computer Science and Director of the Center for Research on Foundations and Applications of Cryptographic Theory (FACT) at the Interdisciplinary Center (IDC; now known as Reichman University) in Herzliya, Israel, where she has been on the faculty since 2015. Dr. Boyle received her Ph.D. from the Massachusetts Institute of Technology (MIT) in mathematics in 2013. Her research has been recognized by numerous awards, including a Google Research Scholar Award in 2021, an Outstanding Researcher Award from IDC in 2019 and a Best Paper award at the International Cryptology Conference (CRYPTO) 2016. For more on her background and areas of research, please read on.

What drew you to the field of cryptography in the first place? Was it the math?

Cryptography is this amazing combination of mathematical beauty together with serious impact to the real world, all encircled with an air of mystery and intrigue. I remember being fascinated by the subject already as a child, reading with my father about the Caesar substitution cipher, the Enigma machine from World War II, and modern notions of public-key cryptography (that you could encrypt a message only to me without us ever meeting beforehand). This curiosity only grew as I got deeper and learned more.

Secure computation, as you defined it at the CyberTech Security Global Event, is about answering the question of “How can you protect data while you’re actually using it.” You also said it goes back a few decades. Who was originally involved in this work?

Exactly. For example, instead of giving your credit card to a company to make an online transaction, or giving your medical data to an insurance company to determine your rates, what if you could instead run a protocol together that enables these outcomes without ever divulging your private information? This is the magic of secure computation.

The notion itself was first introduced in a collection of seminal works from the 1980s, starting with Yao (FOCS 1986), and Goldreich, Micali, Widgerson (STOC 1987), and then within a different setting by Ben-Or, Goldwasser, Widgerson (STOC 1988) and Chaum, Crepeau, Damgard (STOC 1988). These works not only put forth the idea—which itself is a significant contribution—but went as far as to show that for any computation this is actually possible.

Can you talk a little more about the state of the art in secure computation?

At a very high level, there are three approaches that we have right now for achieving secure computation. Two of them go back to the 1980s.

While these original frameworks serve as the common skeleton of most implemented protocols, one of the downsides of these approaches is that they have a lot of overhead in communication. As compared to just exchanging our secret information (which is not secure), these protocols require a rather large bandwidth of messages that we send back and forth, which gets even bigger for more complex applications. This is a huge bottleneck.

Then there’s another approach?

The third main approach that appeared in 2009 is fully homomorphic encryption [Gentry STOC’09]. This is a really strong cryptographic tool that allows you to encrypt data and then compute on it without decrypting it. It turns out that this also gives you a solution for secure computation, and the good news is that it in theory can require very little communication. For example, I could send you an encryption of my input. Then you would be able to homomorphically evaluate the computation and send me back an encryption that I could decrypt and get the final answer.

I was still a student when this came out and it was exciting, partly because of these implications. But long story short, it is still very expensive. In comparison to the original approaches, it requires a lot more computation, and the truth is that even though communication in theory is small, the actual concrete numbers still end up very large.

Overall, in all three existing approaches, we hit limits on how much we’ve been able to optimize. We’ve seen huge progress since the 80s, and a lot of useful outcomes that we’ve gotten out of these works, including even commercially deployed protocols for special targeted applications. But there’s still a big gap before we would be able to use these tools more universally.

Where does your research fit into this development?

One of the directions of my research, which we put forth a few years ago, is a fourth approach to secure computation [Boyle-Gilboa-Ishai CRYPTO’16]. In some sense, fully homomorphic encryption is an overkill for this goal. What we pointed out is that a weaker object, which we call homomorphic secret sharing, is enough to give you secure computation with low communication benefits, but because it’s a weaker object, we were able to build it using different tools, using a wider range of lighter weight constructions. We have already started to see some very interesting applications where it could potentially get both the communication and the computation lower. And the new ideas underlying these constructions have had even more impact in other supporting cryptographic tools.

Is there anything else about your ongoing or forthcoming work that you’d like to add?

I could talk for days. I’ll leave you with a teaser about one new tool we’ve been working to build and use. We call it zero knowledge on distributed data.

At this point, many people have probably heard about zero knowledge: a tool where I can prove to you that I know the solution to a puzzle, without telling you anything about the solution itself. In our new version, we’re pushing things even further. Here, I’ll prove I know the solution to a puzzle to you and your friend—with a twist, that neither you nor your friend even knows what the puzzle is! Instead, you’re holding just the first half of the puzzle, and your friend holds the second half. At the end, both you and your friend will be convinced that I hold a solution to whatever puzzle is formed by putting their pieces together, but without learning anything about the solution or even the puzzle.

As it turns out, this tool has direct applications to boosting the security of secure computation schemes against strong adversarial parties, with low cost overhead. We’ve been exploring this in a recent line of work that includes an upcoming paper at Eurocrypt 2022.

If you don’t mind a question about your collegiate athletic career, which included being named Caltech’s female scholar-athlete of the year, what attracted you to high jumping? You weren’t intrigued by the physics of the sport, were you?

[Laughs] Jumping is such a fun release; I love the sensation of flying in the air. And the events with physics strategy and skill were much more fun: I used to compete in the high jump, triple jump, and the pole vault. So, not exactly sports practice around physics equations at a blackboard, but maybe the next closest thing.