Cryptology ePrint Archive: Report 2021/1554

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:

[ Cryptology ePrint archive ]