Rational Arguments: Single Round Delegation with Sublinear Verification
, University of Aarhus
Date: Friday, February 07, 2014
Time: 10:30 AM to 12:00 PM Note: all times are in the Eastern Time Zone
Host: Vinod Vaikuntanathan, CIS, TOC, CSAIL, MIT
Contact: Holly A Jones, email@example.com
Relevant URL: http://toc.csail.mit.edu/node/454
Speaker URL: None
TALK: Rational Arguments: Single Round Delegation with Sublinear Verification
In this talk I will present Rational Arguments, a new notion that extends the model of Rational Proofs of Azar and Micali into the computational setting. The advantage of rational proofs over their classical counterparts is that they allow for extremely low communication and verification time. We show that this efficiency can be preserved also in the computational setting while additionally decreasing the round complexity.
The low interaction nature of our protocols, along with their sub-linear verification time, make them well suited for delegation of computation. Our rational arguments for languages in NC1 compare favorably to each of the known delegation schemes in at least one aspect; they are simple, rely on standard complexity hardness assumptions, provide a correctness guarantee for all instances, and do not require preprocessing.
This is joint work with Siyao Guo, Alon Rosen and Margarita Vald.
Created by Holly A Jones at Thursday, January 16, 2014 at 9:27 AM.