Technical Program

Paper Detail

Paper Title INTERPOL: Information Theoretically Verifiable Polynomial Evaluation
Paper IdentifierTU3.R5.5
Authors Saeid Sahraei, Amir Salman Avestimehr, University of Southern California, United States
Session Private Computation I
Location Saint Victor, Level 3
Session Time Tuesday, 09 July, 14:30 - 16:10
Presentation Time Tuesday, 09 July, 15:50 - 16:10
Manuscript  Click here to download the manuscript
Abstract 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.