Media contact: Gregory Shook, director of media relations; tele: 413-597-3401; email: [email protected]
WILLIAMSTOWN, Mass., February 10, 2020—Shikha Singh, assistant professor in computer science at Williams College, has been awarded a two-year, $155,000 grant from the National Science Foundation (NSF) to fund her research on verifying that computation outsourced to third-party service providers has been performed correctly. Her work in this area aims to increase understanding of the role of incentives in algorithms, which has wide applications to areas such as crowdsourcing, cloud computing, and social computing.
With the growing popularity of cloud computing, most computation today is not done locally but rather outsourced to third-party service providers, or SPs. Outsourcing computation poses the research problem of how the client outsourcing the computation can verify that it has been performed correctly, without having to redo it. “Most previous work has studied this problem from a security standpoint, assuming that the SPs are malicious or adversarial,” said Singh. “This assumption does not capture the nature of SPs on internet marketplaces, who are often profit-driven, performing computation for money.”
Singh’s project, titled “CRII: AF: RUI: Verifiable Computation Outsourcing: A Non-Cooperative Approach,” approaches the problem of verifying outsourced computation from an economic perspective. In particular, her work focuses on SPs that want to maximize their payment, with the goal of designing payment schemes that directly incentivize correctness. “The advantage of this approach is that it leads to verification protocols that are simple, practical, and require extremely small verification overhead on the part of the client,” said Singh.
Interactive proofs (IP) are a common framework used to study verifiable computation outsourcing. In an IP, the weak client (or verifier) interacts with powerful service providers (or provers) to determine the truthfulness of their claim. Existing IP protocols largely fall into two categories: the cooperative-prover model, such as classical IPs, or the competing-prover model, such as refereed games. In computation-outsourcing applications, the nature of SPs is arguably in the middle of these two extremes, neither cooperative or competitive, but rational—acting to maximize their own payment. The model of non-cooperative rational interactive proofs was introduced recently to capture this middle ground.
Singh’s project aims to take advantage of this new model to design extremely efficient interactive proofs tailored for computation outsourcing. As part of this work, new insights and techniques from game theory and mechanism design will be used to design protocols that achieve extremely small verification overhead compared to existing rational-proof and refereed-games protocols, guarantee robustness against deviating provers, and do not rely on private channels of communication between the verifier and provers.
“My hope is that this project informs the design of future computational-outsourcing platforms and more broadly sheds light on the role of incentives in computation,” said Singh.
Founded in 1793, Williams College is the second-oldest institution of higher learning in Massachusetts. The college’s 2,000 students are taught by a faculty noted for the quality of their teaching and research, and the achievement of academic goals includes active participation of students with faculty in their research. Students’ educational experience is enriched by the residential campus environment in Williamstown, Mass., which provides a host of opportunities for interaction with one another and with faculty beyond the classroom. Admission decisions on U.S. applicants are made regardless of a student’s financial ability, and the college provides grants and other assistance to meet the demonstrated needs of all who are admitted.
Published February 10, 2020