Boston Chapter of IEEE Computer Society and GBC/ACM

6:40 PM, Thursday, 18 May 2023

MIT Room 32-G449 (Kiva) and online via Zoom

Efficient Verification of Computation

Yael Tauman Kalai

Please register in advance for this seminar even if you plan to attend in person at https://acm-org.zoom.us/webinar/register/1016817586906/WN_cpY46yuPSq-LFUC5rLMZtg

After registering, you will receive a confirmation email containing information about joining the webinar.

Indicate on the registration form if you plan to attend in person. This will help us determine whether the room is close to reaching capacity.

We may make some auxiliary material such as slides and access to the recording available after the seminar to people who have registered.

Abstract:

Efficient verification of computation is fundamental to computer science and is at the heart of the P vs. NP question. Recently it has had growing practical significance, especially with the increasing popularity of blockchain technologies and cloud computing. In this talk, I will present schemes for verifying the correctness of a computation. I will discuss both their practical aspects and their impact on quantum complexity, hardness of approximation, and the complexity of Nash equilibrium.

Bio:

Yael Tauman Kalai is Senior Principal Researcher at Microsoft Research New England, adjunct professor in the EECS Dept at MIT, and a member of the Computer Science and Artificial Intelligence Lab (CSAIL).

Yael works on improving the efficiency and privacy of communications through cryptography and has developed methods for verifying the correctness of computation. She developed “doubly efficient” interactive proofs that minimize the computational overhead of using strong devices, machines capable of carrying out more complex cryptographic functions. Succinct proofs offload computations from a weak device to a stronger one, paving the way for faster, more reliable transactions. Ethereum and other blockchain companies have since implemented these proofs to verify the validity of transactions. Yael's work on delegating computation also has applications to cloud computing.

Her master's thesis introduced the concept of ring signatures, a variation of group signatures that preserves the anonymity of individual signers, a concept she co-developed with Ron Rivest and Adi Shamir. This later became incorporated into cryptocurrency systems such as Cryptonote and Monero. Her work on the Fiat-Shamir heuristic established a better understanding of that paradigm’s security issues.

Yael graduated from the Hebrew University of Jerusalem in 1997, worked with Adi Shamir at the Weizmann Institute of Science, earning a master's degree in 2001, and then moved to the Massachusetts Institute of Technology, where she completed her PhD in 2006 with Shafi Goldwasser as her doctoral advisor. She did postdoctoral study at Microsoft Research and the Weizmann Institute before becoming a faculty member at the Georgia Institute of Technology. She has been at Microsoft Research since 2008.

Kalai was an invited speaker on mathematical aspects of computer science at the 2018 International Congress of Mathematicians. Her master's thesis introducing ring signatures won an outstanding master's thesis award and her MIT PhD dissertation was awarded the George M. Sprowls Award for Outstanding PhD Thesis in Computer Science. She was co-chair of the Theory of Cryptography Conference in 2017 and chair of the Innovations in Theoretical Computer Science (ITCS) Conference in 2023. She is a fellow of the International Association of Cryptographic Research (IACR), and was recently awarded the 2022 ACM Prize in Computing "for breakthroughs in verifiable delegation of computation and fundamental contributions to cryptography".

This joint meeting of the Boston Chapter of the IEEE Computer Society and GBC/ACM will be hybrid (in person and online), our first attempt to get back to normal after the COVID-19 lockdown.

Up-to-date information about this and other talks is available online at https://ewh.ieee.org/r1/boston/computer/. You can sign up to receive updated status information about this talk and informational emails about future talks at https://mailman.mit.edu/mailman/listinfo/ieee-cs, our self-administered mailing list.

Updated: April 21, 2023--webbot bot="TimeStamp" i-checksum="16995" endspan -->.