VESPo: Verified Evaluation of Secret Polynomials. (arXiv:2110.02022v2 [cs.CR] UPDATED)

We consider the problem of efficiently evaluating a secret polynomial at a
given public point, when the polynomial is stored on an untrusted server. The
server performs the evaluation and returns a certificate, and the client can
efficiently check that the evaluation is correct using some pre-computed keys.
Our protocols support two important features: the polynomial itself can be
encrypted on the server, and it can be dynamically updated by changing
individual coefficients cheaply without redoing the entire setup. As …