Rational Arguments: Single Round Delegation with Sublinear Verification

Abstract:

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.