Yael Tauman Kalai

Digital Library

ACM Prize in Computing

USA - 2022

citation

For breakthroughs on verifiable delegation of computation and fundamental contributions to cryptography

Yael Tauman Kalai has made fundamental advances to cryptography through groundbreaking work in verifiable delegation of computation, eliminating interaction in cryptographic protocols, leakage-resilient cryptography, and interactive coding theory. Although her work is theoretical in nature, it has had a profound impact on practical applications in cryptography and blockchain technologies.

Kalai devised a method for generating "succinct proofs" that certify the correctness of any computation. This method enables a weak device to offload any computation to a stronger device in a way that enables the results to be efficiently checked for correctness. Such succinct proofs have been used by numerous blockchain companies (including Ethereum) to certify transaction validity and thereby overcome key obstacles in blockchain scalability, enabling faster and more reliable transactions. Kalai's research has provided essential definitions, key concepts, and inventive techniques to this domain. More specifically, Kalai's work pioneered the study of "doubly efficient" interactive proofs, which ensure that the computational overhead placed on the strong device is small (nearly linear in the running time of the computation being proved). In contrast, previous constructions incurred an overhead that is highly exponential in the space of the computation. Kalai's work transformed the concept of delegation from a theoretical curiosity to the realm of practice. Her subsequent work used cryptography to develop certificates of computation, eliminating the need for back-and-forth interaction. This work used insights from quantum information theory, specifically "non-signaling" strategies, to construct a one-round delegation scheme for any computation. These schemes have led to a body of work on delegation, including theoretical advancements, applied implementations, and real-world deployment.

Kalai's other important contributions include her breakthrough work on the security of the "Fiat-Shamir paradigm," a general technique for eliminating interaction from interactive protocols. This paradigm is extensively utilized in real-world applications, including in the most prevalent digital signature scheme (ECDSA), which is used by all iOS and Android mobile devices. Despite its widespread adoption, its security has been poorly understood. Kalai's research established a solid foundation for understanding the security of this paradigm. In addition, she co-pioneered the field of leakage resilient cryptography and solved a long-standing open problem in interactive coding theory, showing how to convert any interactive protocol into one that is resilient to a constant fraction of adversarial errors, while increasing the communication complexity by at most a constant factor and the running time by at most a polynomial factor. Kalai's extensive work in the field of cryptography has helped shape modern cryptographic practices and provided a strong foundation for further advancements.

Press Release

Background