### How to Claim a Computational Feat

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

Available format(s)
Category
Cryptographic protocols
Publication info
Preprint. MINOR revision.
Keywords
proof of workhashing
Contact author(s)
david naccache @ ens fr
History
Short URL
https://ia.cr/2021/1554

CC BY

BibTeX

@misc{cryptoeprint:2021/1554,
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{https://eprint.iacr.org/2021/1554}},
url = {https://eprint.iacr.org/2021/1554}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.