Paper 2015/1058

Rational Sumchecks

Siyao Guo, Pavel Hubacek, Alon Rosen, and Margarita Vald

Abstract

Rational proofs, 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. In recent work, Guo et al. (ITCS 2014) demonstrated their relevance to delegation of computation by showing that, if the rational prover is additionally restricted to being computationally bounded, then every language in NC1 admits a single-round delegation scheme that can be verified in sublinear time. 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.

Metadata
Available format(s)
PDF
Publication info
Published by the IACR in TCC 2016
Keywords
rational proofsmulti-prover rational proofsrational argumentssumcheck protocolverifiable delegation of computationcomposition of rational protocols
Contact author(s)
syguo @ cse cuhk edu hk
pavel hubacek @ weizmann ac il
alon rosen @ idc ac il
margarita vald @ cs tau ac il
History
2015-10-30: received
Short URL
https://ia.cr/2015/1058
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/1058,
      author = {Siyao Guo and Pavel Hubacek and Alon Rosen and Margarita Vald},
      title = {Rational Sumchecks},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1058},
      year = {2015},
      note = {\url{https://eprint.iacr.org/2015/1058}},
      url = {https://eprint.iacr.org/2015/1058}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.