**How to Claim a Computational Feat**

*Clémence Chevignard and Rémi Géraud-Stewart and Antoine Houssais and David Naccache and 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$.

**Category / Keywords: **cryptographic protocols / proof of work, hashing

**Date: **received 26 Nov 2021

**Contact author: **david naccache at ens fr

**Available format(s): **PDF | BibTeX Citation

**Version: **20211129:122246 (All versions of this report)

**Short URL: **ia.cr/2021/1554

[ Cryptology ePrint archive ]