  We study the problem of verifiable polynomial evaluation in the user-server
and multi-party setups. We propose {INTERPOL}, an information-theoretically
verifiable algorithm that allows a user to delegate the evaluation of a
polynomial to a server, and verify the correctness of the results with high
probability and in sublinear complexity. Compared to the existing approaches
which typically rely on cryptographic assumptions, {INTERPOL} stands out in
that it does not assume any computational limitation on the server. {INTERPOL}
relies on decomposition of polynomial evaluation into two matrix
multiplications, and injection of computation redundancy in the form of locally
computed parities with secret coefficients for verification. We show that
{INTERPOL} has several desirable properties such as adaptivity and public
verifiability. Furthermore, by generalizing {INTERPOL} to a multi-party setting
consisting of a network of $n$ untrusted nodes, where each node is interested
in evaluating the same polynomial, we demonstrate that we can achieve an
overall computational complexity comparable to a trusted setup, while
guaranteeing information-theoretic verification at each node.
