Verifiable Delegation of Polynomials

Abstract

Verifiable computation allows a computationally weak client to outsource evaluation of a function on many inputs to a powerful but untrusted server. The client invests a large amount of offline computation in an amortized manner to obtain an encoding of its function which is then given to the server. The server returns both the evaluation result of the function on the client's input and a proof with which the client can verify the correctness of the evaluation using substantially less effort than doing the evaluation on its own from scratch. In this paper a verifiable delegation of polynomials is proposed based on the integer factorization problem. In the computation procedure, the computation polynomial and the verification polynomial are distinguishable, the wrong result and the result of other inputs will incur a validation failure. And last, the client can verify the result efficiently.