The problem of securely outsourcing data and computation has received widespread attention due to the rise of cloud computing: a paradigm where businesses lease computing resources from a service rather than maintain their own computing infrastructure. These scenarios introduce new security problems: in particular how do we trust the integrity of data and computation that are not under our own control. This project deals with these problems by considering methods, adapted from the world of economics, to incentivize parties to behave correctly during the execution of a computation. This research could have a transformative effect on the way computations are outsourced in many scenarios where a fully malicious adversary does not need to be considered. The proposed research serves two complementary functions: to address problems which are crucial to securing our computing infrastructure, and to advance a cross-disciplinary scientific approach. The project explores the notion of Rational Proof, where the execution of a computational problem is rewarded with a randomized function, maximized in expectation when the computation is performed correctly. We show that current notions of Rational Proofs do not satisfy basic compositional properties for the case in which many computations are outsourced. For some protocols in the literature we show that a fast but incorrect answer is more remunerable for the prover, by allowing him or her to solve more problems and collect more rewards.
EAGER: Economic Incentives for Correct Outsourced Computation via Rational Proofs