Professor Tal Rabin is one of the latest researchers to receive ACM’s 2021 STOC Test of Time Award. Co-published with her then Ph.D. advisor, Michael Ben-Or, Professor Rabin’s “Verifiable secret-sharing and multiparty protocols with honest majority” (STOC 1989) was one of three papers to be recognized for its groundbreaking contributions 30 years later.
This year marks the inaugural issuing of the award by ACM’s Special Interest Group on Algorithms and Computation Theory (SIGACT), which recognizes papers published in the Proceedings of the Annual ACM Symposium on Theory of Computing.
Described by Forbes as “a genius for working relationships, which she applies to algorithms as well as team building,” Professor Rabin used a shared attribute of working society to describe the paper’s thesis.
“Let’s say there are three people and together we want to find out what is the sum of all our salaries, but I don’t want to tell you my salary,” said Rabin. “You don’t want to tell me your salary and we don’t want to tell the third person our salary, but still we want to know the sum of all three salaries. How do we compute functions here?”
With the function representing the sum of all individual salaries, Professor Rabin’s hypothetical asserts that previous research before her paper could account for 3 faulty parties out of 11, and still provide accurate computations. Professor Rabin’s paper proves that one could get accurate computations with up to 5 faulty parties. One could still calculate the sum of all the salaries, “even if some of the people are trying to foil the computation, or to learn more than what is supposed to be learned,” said Rabin.
Professor Rabin credits this research, in combination with the works of the other two teams awarded with 30-year honor, with opening up the field of information theoretic multi-party computations.
“It opened so many interesting questions of how fast can we compute, how efficient can we be? Can we do some things better?” said Rabin. “These results proved to be fundamental and enabled a lot of growth afterwards.”
According to Professor Rabin, the paper is not only responsible for laying crucial foundations in the computational theory field, but also in her own professional and private life.
“I’m so honored and happy to be in this group,” said Rabin. “I wrote to Michael, ‘thank you really for suggesting this problem to me.’ I wrote to him, ‘it really defined my life. It impacts my life in a very profound way.’”