Paper 2021/1554

How to Claim a Computational Feat

Clémence Chevignard, Rémi Géraud-Stewart, Antoine Houssais, David Naccache, and Edmond de Roffignac


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$.

Available format(s)
Cryptographic protocols
Publication info
Preprint. MINOR revision.
proof of workhashing
Contact author(s)
david naccache @ ens fr
2021-11-29: received
Short URL
Creative Commons Attribution


      author = {Clémence Chevignard and Rémi Géraud-Stewart and Antoine Houssais and David Naccache and Edmond de Roffignac},
      title = {How to Claim a Computational Feat},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1554},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.