People of ACM - Yael Tauman Kalai
May 11, 2023
For someone who is unfamiliar with your field, what are the goals of those working on the mathematical foundations of cryptography?
Our objective is to promote the secure and effective utilization of cryptography. We focus on developing cryptographic primitives that offer provable security, or at the very least, ones for which we possess a comprehensive understanding of the security-efficiency tradeoffs. Furthermore, we aim to understand the fundamental limits of what is possible—an endeavor that requires overcoming barriers, devising innovative concepts, and constructing clever protocols.
How does being able to certify the correctness of any computation aid in practical applications of cryptography? Will you give an example?
Certifying the correctness of computation is valuable not only for cryptographic applications but in any system that involves computationally strong untrusted devices or any highly distributed platform. By providing certificates of correctness, we can boost efficiency by eliminating the necessity for all parties to verify the correctness of the computation from scratch instead, they can simply check the certificate's validity, thereby enhancing both scalability and usability. A practical example of such certificates in use today is within the scope of blockchain technologies. Platforms like Ethereum employ these certificates to "shorten" the chain by generating a "digest" of it and using succinct certificates to validate transactions. I anticipate that the adoption of succinct certificates will expand as the popularity of various untrusted machine learning algorithms, such as large language models, continues to grow.
The relevance of cryptography in this context is two-fold. Firstly, the security of such succinct certificates (i.e., the hardness to fake certificates for false computations) relies on computational assumptions, such as the difficulty of factoring large numbers, which are foundational to cryptography. Secondly, it is often desirable to ensure that these certificates do not leak any sensitive information. To achieve this, a zero-knowledge component is incorporated, providing an additional layer of cryptographic security.
One exciting area of cryptography is the problem of obfuscation. Will you give a brief overview of the problem of obfuscation and what might be some applications of further research advances?
Program obfuscation is one of the most fascinating and challenging problems in cryptography today. The objective is to convert any program into a "garbled" version that preserves the original's input/output behavior while hiding its internal mechanics. Ideally, the sole information disclosed should be the input/output access. As a community, we have been captivated by this problem for over two decades. Initially, the feasibility of an obfuscation system was uncertain, as early findings were negative. For a lengthy period, we lacked even a heuristic approach to address this issue. However, we now possess obfuscation methods that are provably secure under standard assumptions. Although these techniques are currently far from practical, refining them to edge closer to the realm of practicality remains a significant unresolved challenge in the field.
The Theory of Computation is an area of computer science that might not get as much attention as other areas, such as AI. For an undergraduate trying to decide which area of computer science they might want to pursue in graduate school, what would you say to encourage them to at least explore what your field has to offer?
I always encourage students to follow their heart when choosing a research area. I believe that each individual has an innate understanding of their strengths and weaknesses even if they may not be able to articulate them. Furthermore, I believe that a student's passion for the problems they tackle is of utmost importance. It is not uncommon for students to explore different fields before discovering the one that resonates with them the most. In my case, cryptography captured my interest because I like deep mathematical concepts and I am motivated by real-word applications. The field of cryptography successfully combines both aspects, making it a fulfilling choice for me.
Yael Tauman Kalai is a Senior Principal Researcher at Microsoft Research and an Adjunct Professor at the Massachusetts Institute of Technology (MIT). Her main research interests are cryptography, the Theory of Computation, and security and privacy. She is especially known for her work in verifiable delegation of computation, where she has developed succinct proofs that certify the correctness of any computation. In addition to making breakthroughs in the mathematical foundations of cryptography, her proofs have been practically useful in areas such as blockchain and cryptocurrency.
She was recently named the recipient of the 2022 ACM Prize in Computing for breakthroughs in verifiable delegation of computation and fundamental contributions to cryptography.