Welcome to the resource topic for 2021/1554
Title:
How to Claim a Computational Feat
Authors: Clémence Chevignard, Rémi Géraud-Stewart, Antoine Houssais, David Naccache, Edmond de Roffignac
Abstract:Consider some user buying software or hardware from a provider. The provider claims to have subjected this product to a number of tests, ensuring that the system operates nominally. How can the user check this claim without running all the tests anew? The problem is similar to checking a mathematical conjecture. Many authors report having checked a conjecture C(x)=\mbox{True} for all x in some large set or interval U. How can mathematicians challenge this claim without performing all the expensive computations again? This article describes a non-interactive protocol in which the prover provides (a digest of) the computational trace resulting from processing x, for randomly chosen x \in U. With appropriate care, this information can be used by the verifier to determine how likely it is that the prover actually checked C(x) over U. Unlike traditional'' interactive proof and probabilistically-checkable proof systems, the protocol is not limited to restricted complexity classes, nor does it require an expensive transformation of programs being executed into circuits or ad-hoc languages. The flip side is that it is restricted to checking assertions that we dub \emph{refutation-precious}‘’: expected to always hold true, and such that the benefit resulting from reporting a counterexample far outweighs the cost of computing C(x) over all of U.
ePrint: https://eprint.iacr.org/2021/1554
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .