ACM Prize to Yael Kalai

Yael Kalai has just been named the winner of the 2022 ACM Prize. She works at Microsoft Research.

Today we congratulate her, say a little about her work, and riff on some related and “unrelated” matters.

The prize cites Kalai for her work on cryptography. Her work is immediately practical. It provides both ways to speed up interactive protocols and to verify the results. Two ways of speeding up the kind of protocols we engage in daily are:

1. Reduce the number of rounds of interaction needed.

2. Shift the computational burden from the weaker party (exemplified by your credit card chip) to the stronger party—without allowing the latter more ways to be malicious.

One also needs to devise and provide an efficient certificate that the security needs have been met.

Her Work

Kalai’s work on objective 1 starts with a paradigm originally expounded by Amos Fiat and Adi Shamir in the 1980s:

An interactive round in which Arthur challenges Merlin with a string he chose randomly from public coins can be replaced by nonteractive requests to a random oracle. The oracle in turn can be simulated via a cryptographically strong hash function.

The second clause is the delicate one. How can we know, in a particular application, that a particular hash function does not have correlations that could be exploited by malicious choices of plaintext or seed strings? She and Shafi Goldwasser, her PhD advisor, showed cases where a 3-round protocol secure in the random oracle model becomes insecure under cases of this transformation.

However, in a series of papers culminating in a Part I and a Part II, she and coauthors designed cases that work under progressively more reasonable hardness assumptions. (Note: the date on the “Part II” paper is three days earlier than that on the “Part I”–a good solution to a problem we noted at the end of this post.)

Objective 2 not only runs the risk of leakage in shifting the party who executes the computation, it involves issues of trust. How does the one who delegated the task know the result is correct, without having done the computation? This leads to issues of proving computations correct that we have mentioned, but with a twist: both the computation and the proof needs to be real-time efficient to generate. Her many papers on this (ACM features these two) are well represented in a survey she presented at the 2018 International Congress of Mathematicians. Its abstract proclaims:

Efficient verification of computation, also known as delegation of computation, is one of the most fundamental notions in computer science, and in particular it lies at the heart of the P vs. NP question.

P = NP: An Omen?

Her survey was unveiled “exclusively for our readers” in a January 6, 2018 post by Gil Kalai, along with two photos of adoring father(-in-law)/grandparent type. We hasten to add that all this is not just about how “P=NP?” captures the question of whether it is as easy to generate a proof as to verify it. Much of Yael Kalai’s work depends on hardness assumptions that vanish if in fact P equals NP (with relevant efficiency).

Thinking of Gil Kalai makes us leap to two other topics that are variously related and “unrelated.” Gil recently featured the following photo from street protests in Israel on his blog:

The photo was also picked up and commented on by Scott Aaronson on his blog. Gil added:

Whether the picture is genuine or not, it shows the anarchist nature of at least some of the protestors. (We know for sure that some computer scientists were there.) I am not sure if a proof of this bold claim was also provided.

Lightheartedness aside, we wonder if this is an omen of growing public awareness of the connection of our field’s signature question not only to the security workings of governments, but to the walks of life represented by Yael Kalai’s applications.

Your humble bloggers face a kind of verification problem with nearly every post: how to pin down and attest basic facts. Here we remembered writing in 2014—correctly—that “Yael Kalai [is] not related to our friend Gil Kalai.” But learning that Yael Tauman married Adam Kalai (which is attested in many places) added another thing to check. The passage of time—and Gil’s photos—revived doubt.

Heretofore we’ve refined the art of crafting Google queries to filter out professional information and bring what we want to the top page of hits. But in theory, such quests are better posed directly to the likes of ChatGPT. So I (Ken) did so, first to the free GPT-3.5:

Wait a second—has ChatGPT not been briefed on the injunction against incestuous marriage? Or have too many Roman and Greek emperors dominated its data? When Moses flung down and broke the stone tablets in exasperation, was it over chatbots? I tried the pay-grade version and got a different—but not better—answer:

Nor did GPT-4 correct my typo of an extra ‘n.’ Happily, Gil’s mention of the fourth Kalai—and confirmation gratia Lance Fortnow that I found via Google—enabled me to confront GPT-4 with a pertinent question. This produced an all-too-human reaction:

“Confusion,” indeed? At the right are little hands to upvote or downvote responses. I upvoted the true one and gave the reason as, “it is true.” Then I down-voted the false one and clicked a reason button saying, “This isn’t true.” To my consternation a new box appeared:

In words that won the 2016 Literature Nobel, no direction home. It seems our task of educating GPT will pale that in the wonderful play and movie Educating Rita.

Open Problems

Should we have been more worried if P=PSPACE was sprayed in the street? Or if a proof was referenced somehow? As for GPT, it calls to our minds some other words that have not yet won a Literature Nobel.

[some word tweaks]