Dissertations, Theses, and Capstone Projects

Date of Degree

9-2018

Document Type

Dissertation

Degree Name

Ph.D.

Program

Computer Science

Advisor

Rosario Gennaro

Committee Members

Itai Feigenbaum

Mariana Raykova

William Skeith III

Subject Categories

Information Security | Other Computer Sciences | Theory and Algorithms

Keywords

rationality, cloud computing, verifiable computation, cryptography, homomorphic encryption

Abstract

In this thesis, we study protocols for delegating computation in a model where one of the parties is rational. In our model, a delegator outsources the computation of a function f on input x to a worker, who receives a (possibly monetary) reward. Our goal is to design very efficient delegation schemes where a worker is economically incentivized to provide the correct result f(x). In this work we strive for not relying on cryptographic assumptions, in particular our results do not require the existence of one-way functions.

We provide several results within the framework of rational proofs introduced by Azar and Micali (STOC 2012).We make several contributions to efficient rational proofs for general feasible computations.

First, we design schemes with a sublinear verifier with low round and communication complexity for space-bounded computations. Second, we provide evidence, as lower bounds, against the existence of rational proofs: with logarithmic communication and polylogarithmic verification for P and with polylogarithmic communication for NP.

We then move to study the case where a delegator outsources multiple inputs. First, we formalize an extended notion of rational proofs for this scenario (sequential composability) and we show that existing schemes do not satisfy it. We show how these protocols incentivize workers to provide many ``fast'' incorrect answers which allow them to solve more problems and collect more rewards. We then design a d-rounds rational proof for sufficiently ``regular'' arithmetic circuit of depth d = O(log(n)) with sublinear verification. We show, that under certain cost assumptions, our scheme is sequentially composable, i.e. it can be used to delegate multiple inputs. We finally show that our scheme for space-bounded computations is also sequentially composable under certain cost assumptions.

In the last part of this thesis we initiate the study of Fine Grained Secure Computation: i.e. the construction of secure computation primitives against ``moderately complex" adversaries. Such fine-grained protocols can be used to obtain sequentially composable rational proofs. We present definitions and constructions for compact Fully Homomorphic Encryption and Verifiable Computation secure against (non-uniform) NC1 adversaries. Our results hold under a widely believed separation assumption implied by L ≠NC1 . We also present two application scenarios for our model: (i) hardware chips that prove their own correctness, and (ii) protocols against rational adversaries potentially relevant to the Verifier's Dilemma in smart-contracts transactions such as Ethereum.

Download

Share

COinS