INTERPOL: Information Theoretically Verifiable Polynomial Evaluation

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.