We extend the Guo et al. result by constructing a single-round delegation scheme with sublinear verification for all languages in P. Our main contribution is the introduction of {\em rational sumcheck protocols}, which are a relaxation of classical sumchecks, a crucial building block for interactive proofs. Unlike their classical counterparts, rational sumchecks retain their (rational) soundness properties, {\em even if the polynomial being verified is of high degree} (in particular, they do not rely on the Schwartz-Zippel lemma). This enables us to bypass the main efficiency bottleneck in classical delegation schemes, which is a result of sumcheck protocols being inapplicable to the verification of the computation's input level.
As an additional contribution we study the possibility of using rational proofs as efficient blocks within classical interactive proofs. Specifically, we show a composition theorem for substituting oracle calls in an interactive proof by a rational protocol.
Category / Keywords: rational proofs; multi-prover rational proofs; rational arguments; sumcheck protocol; verifiable delegation of computation; composition of rational protocols Original Publication (in the same form): IACR-TCC-2016 Date: received 30 Oct 2015 Contact author: syguo at cse cuhk edu hk, pavel hubacek@weizmann ac il, alon rosen@idc ac il, margarita vald@cs tau ac il Available format(s): PDF | BibTeX Citation Version: 20151030:193342 (All versions of this report) Short URL: ia.cr/2015/1058 Discussion forum: Show discussion | Start new discussion