[Busec] Today at 11: Babis Papamanthou

Leonid Reyzin reyzin at cs.bu.edu
Tue Apr 10 09:26:59 EDT 2012


Publicly Verifiable Delegation of Computation (with I/O Privacy)
Charalampos Papamanthou, UC Berkeley
MCS148, 11AM Tuesday

We study publicly verifiable computation, which generalizes verifiable
computation in the secret key setting and authenticated data
structures. In publicly verifiable computation, a trusted source
outsources an application (algorithm) to an untrusted server. Any
client can ask the server to run the application over some given
inputs, and the server can produce a witness vouching for the
correctness of the outcome.

We propose publicly verifiable computation schemes supporting
expressive manipulations over multivariate polynomials, such as
polynomial evaluation and differentiation. Our scheme allows a client
to verify the outcome in time proportional to the size of the input,
and not depending on the degree and the description of the polynomial,
i.e., in asymptotically less time than performing the computation
locally. Moreover, our scheme allows the source to efficiently update
the polynomial coefficients without performing expensive
recomputations proportional to the size of the polynomial. Finally, we
extend our core scheme to provide input/output privacy (I/O privacy)
on top of verifiability, enabling verifiable data analysis across
clients and in a private way. Applications of verifiable polynomial
operations in finite fields include verifiable statistical
computations and error correcting codes algorithms.

Joint work with Elaine Shi and Roberto Tamassia
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://cs-mailman.bu.edu/pipermail/busec/attachments/20120410/af620f2b/attachment.html 


More information about the Busec mailing list