INTERPOL: Information Theoretically Verifiable Polynomial Evaluation
This addresses the need for secure and efficient verification of delegated computations without relying on cryptographic assumptions, which is incremental as it builds on existing verifiable computation methods.
The paper tackles the problem of verifiable polynomial evaluation in user-server and multi-party setups by proposing INTERPOL, an information-theoretically verifiable algorithm that allows users to delegate polynomial evaluation to servers and verify results with high probability and sublinear complexity, achieving computational complexity comparable to trusted setups in multi-party settings.
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.