Paper 2023/586

A Novel Preprocessing-Free Proofless Verifiable Computation Scheme from Integer Factoring

Alex Dalton, Imperial College London
David Thomas, University of Southampton
Peter Cheung, Imperial College London

Verifiable Computation (VC) schemes provide a mechanism for verifying the output of a remotely executed program. These are used to support computing paradigms wherein a computationally restricted client, the Verifier, wishes to delegate work to a more powerful but untrusted server, the Prover. The Verifier wishes to detect any incorrect results, be they accidental or malicious. The current state-of-the-art is only close-to-practical, usually because of a computationally demanding setup which must be amortised across repeat executions. We present a VC scheme for verifying the output of arithmetic circuits with a small one-time setup, KGen, independent of the size of the circuit being verified, and a insignificantly small constant program specific setup, ProbGen. To our knowledge our VC scheme is the first built from the hardness of integer factoring, a standard cryptographic assumption. Our scheme has the added novelty that the proofs are simply the raw output of the target computation, and the Prover is in effect blind to the fact they are taking part in a VC scheme at all. Although our scheme has worse asymptotic performance than the state-of-the-art it is particularly well suited for verifying one-shot programs and the output of large integer polynomial evaluation.

Available format(s)
Cryptographic protocols
Publication info
Verifiable computationCloud computingDelegated computingDistributed computing
Contact author(s)
akd19 @ ic ac uk
d b thomas @ southampton ac uk
p cheung @ imperial ac uk
2023-12-22: last of 2 revisions
2023-04-24: received
See all versions
Short URL
Creative Commons Attribution


      author = {Alex Dalton and David Thomas and Peter Cheung},
      title = {A Novel Preprocessing-Free Proofless Verifiable Computation Scheme from Integer Factoring},
      howpublished = {Cryptology ePrint Archive, Paper 2023/586},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.