Computational integrity with a public random string from quasi-linear PCPs.

A party executing a computation on behalf of others may benefit from misreporting its output. Cryptographic protocols that detect this can facilitate decentralized systems with stringent computational integrity requirements. For the computation’s result to be publicly trustworthy, it is moreover imperative to usepublicly verifiable protocols that have no “backdoors” or secret keys that enable forgery.