Verifiable Polynomial Evaluation

Cryptographic scheme that enables a cloud provider to evaluate a polynomial over an input received from the user and to prove to a user that the output is actually correct. We consider a scenario whereby a user wishes to outsource a high-degree polynomial P to the cloud server. Further, a queried requests the evaluation of this polynomial over some inputs x. In addition to the output and the server also provides a proof p on the correctness of the output. Finally, the verifier receiving the output and the proof verifies p and concludes whether y equals P(x). The goal of the solution is to render the verification of the proof as efficient as possible.