Rational Arguments: Single Round Delegation with Sublinear Verification: Pavel Hubacek, Aarhus and Northeastern
- 10:00 am on Wednesday, October 23, 2013
- 11:30 am on Wednesday, October 23, 2013
- MCS 137
Abstract: Rational proofs, recently introduced by Azar and Micali (STOC 2012), are a variant of interactive proofs in which the prover is neither honest nor malicious, but rather rational. The advantage of rational proofs over their classical counterparts is that they allow for extremely low communication and verification time. Azar and Micali demonstrated their potential by giving a one message rational proof for #P, in which the verifier runs in time O(n), where n denotes the instance size. In a follow-up work (EC 2013), Azar and Micali proposed „super-efficient“ and interactive versions of rational proofs and argued that they capture precisely the class TC0 of constant-depth, polynomial-size circuits with threshold gates. In this work, we show that by considering rational arguments, in which the prover is additionally restricted to be computationally bounded, the class NC1, of search problems computable by log-space uniform circuits of O(log n)-depth, admits rational protocols that are simultaneously one-round and polylog(n) time verifiable. This demonstrates the potential of rational arguments as a way to extend the notion of „super-efficient“ rational proofs beyond the class TC0. The low interaction nature of our protocols, along with their sub-linear verification time, make them well suited for delegation of computation. While they provide a weaker (yet arguably meaningful) guarantee of soundness, they compare favorably with 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. Our rational arguments are constructed in two steps. We first design a multi-round rational proof and then collapse it into a single round argument. In doing so, we identify the gap between the reward given to a truthful prover in the proof and the one given to a dishonest one as a key parameter in the quality of the resulting argument. We leave it as an intriguing open problem to determine whether one could „scale up“ the underlying proofs to classes beyond NC1, and potentially even beyond P (thus bypassing known impossibility results), and point out some limitations in doing so for non-trivial languages. This is a joint work with Siyao Guo, Alon Rosen and Margarita Vald.