<div class="gmail_quote"><br>
Publicly Verifiable Delegation of Computation (with I/O Privacy)<br>
Charalampos Papamanthou, UC Berkeley<br>
MCS148, 11AM Tuesday<br>
<br>
We study publicly verifiable computation, which generalizes verifiable<br>
computation in the secret key setting and authenticated data<br>
structures. In publicly verifiable computation, a trusted source<br>
outsources an application (algorithm) to an untrusted server. Any<br>
client can ask the server to run the application over some given<br>
inputs, and the server can produce a witness vouching for the<br>
correctness of the outcome.<br>
<br>
We propose publicly verifiable computation schemes supporting<br>
expressive manipulations over multivariate polynomials, such as<br>
polynomial evaluation and differentiation. Our scheme allows a client<br>
to verify the outcome in time proportional to the size of the input,<br>
and not depending on the degree and the description of the polynomial,<br>
i.e., in asymptotically less time than performing the computation<br>
locally. Moreover, our scheme allows the source to efficiently update<br>
the polynomial coefficients without performing expensive<br>
recomputations proportional to the size of the polynomial. Finally, we<br>
extend our core scheme to provide input/output privacy (I/O privacy)<br>
on top of verifiability, enabling verifiable data analysis across<br>
clients and in a private way. Applications of verifiable polynomial<br>
operations in finite fields include verifiable statistical<br>
computations and error correcting codes algorithms.<br>
<br>
Joint work with Elaine Shi and Roberto Tamassia<br>
<br></div>