Cryptography, the study of finding secure methods of communication, may seem to many of us as, well, cryptic. But in spite of its more theoretical and foundational nature in computing, cryptography is more important now than ever in securing private communication and other types of information that are no longer stored on our own private machines. Add in constantly evolving privacy policies and new communication and transaction technologies to the mix, and the potential impact of cryptography in the real world is immense.
Professor Yael Kalai of MIT CSAIL and Senior Principal Researcher at Microsoft Research New England is a cryptographer and theoretical computer scientist working on state-of-the-art ways of securing computation.
Cryptography has come a long way in the last 30 years, starting with the concept of proofs and how we view them shifting from classical proofs to zero-knowledge interactive proofs, which CSAIL researchers helped pioneer and continue to work on in the Theory of Computation research group, of which Prof. Kalai is a part.
The MIT researchers noticed that the interactive proofs would interact with each other. “It’s some kind of interactive process that allows for zero-knowledge,” says Prof. Kalai. “But later, what was also noticed is that this is a much more powerful proof system — namely, that we can actually make proofs much more succinct, much shorter, much more easily verifiable.”
This discovery, she says, gives you the ability to hide information with the zero-knowledge aspect, which cryptography is good at doing. “The other thing it’s doing, which is not often thought of as a cryptographic thing, is it allows for much more efficient verification,” Prof. Kalai explains. “Before, to argue, to give you a proof of something, you would need to read 100 pages. Now you need to read very little communication, but you need to interact very efficiently. So this idea of interactive proofs has proven very useful.”
Zero-knowledge interactive proofs have opened up a wide range of real-world applications in cryptography, including cryptocurrencies, which use these proofs to ensure privacy.
“The problem with these cryptocurrencies is that they’re public ledgers, and these public ledgers store all our transactions,” she says. This can be a problem when you are associated with a public key, even if you are anonymous as a public key holder, because others can trace this information back to you through your transactions, so getting secrecy in cryptocurrency is important.
She adds that there are several cryptocurrency companies, some of which started at MIT, that use these zero-knowledge proofs. Adding these succinct proofs helps not only in privacy but also in efficiency. So instead of going back to verify where the cryptocurrency came from and was not double-spent each time, you can add a little certificate, a succinct, interactive proof that can be put on the blockchain.
Another recent success for cryptography is the notion of fully homomorphic encryption. This type of encryption “allows us to encrypt a message, but then allows us to do computation on this message underneath the encryption,” explains Prof. Kalai. “So we can compute on it without actually knowing anything about the computation itself.” Homomorphic encryption has cryptocurrency applications, and it is also very useful for health care data research, in which data privacy is essential. “We want to do some statistics and learn information, so you want to do things under the hood of an encryption scheme,” she says, without compromising the private health information.
In her work between CSAIL and Microsoft Research, Prof. Kalai enjoys collaborating with others in the community of theoretical cryptography. “One thing that excites me is to work with the students and see a spark in their eyes when they have a result,” she says.
In addition, she says that “at the end of the day, my work is to advance the state-of-the-art and try to have an impact… The work I do in collaboration between MIT and Microsoft Research goes beyond specific projects; it is about the connection of people and minds: sitting together with brilliant people from both MIT and Microsoft Research and brainstorming. I think the work is really valued in both places; it’s a win-win, and I think both institutions view it that way.”
This collaboration allows CSAIL students to visit and learn about Microsoft, and Prof. Kalai has been involved in co-organized seminars, workshops, and crypto days.
Prof. Kalai also enjoys collaborating on larger initiatives across MIT, such as the Private Automated Contact Tracing (PACT) project, which is led by CSAIL, the MIT Internet Policy Research Initiative, Massachusetts General Hospital Center for Global Health, and the MIT Lincoln Laboratory. For her part in PACT, Prof. Kalai is working on the best algorithm to ensure privacy for digital contact tracing.
Similar to the challenges of cryptocurrency and other cryptography applications, digital contact tracing comes with privacy challenges, such as when and how to reveal if someone has come into contact with someone who tested positive for COVID-19, without revealing their identity or giving other users the ability to trace it back to them. If your cell phone is emitting Bluetooth signals or “chirps,” Prof. Kalai says “the basic thing you want to do is ensure that the chirps that people hear are not traceable… The chirps need to be changing all the time.” There are also company policy constraints regarding using location data to consider, as well as challenges in making the app simple to use and understand.
“A lot of things come into play while working on projects like this that I’m not used to thinking about, so that’s really fun,” says Prof. Kalai. “Also, the collaboration between policy people and technical people, health workers, contact tracers, a whole new kind of collaboration with a very diverse set of people, was really interesting.”