2020 IEEE International Symposium
on Information Theory
21-26 June 2020 • Los Angeles, California, USA
| Paper ID | T.1.3 | ||
| Paper Title | Interactive Verifiable Polynomial Evaluation | ||
| Authors | Saeid Sahraei, Qualcomm Technologies, Inc., United States; Mohammad Ali Maddah-Ali, Nokia Bell Labs, United States; Salman Avestimehr, University of Southern California, United States | ||
| Session | T.1: Complexity and Computation Theory | ||
| Presentation | Lecture | ||
| Track | Topics in Information Theory | ||
| Manuscript | Click here to download the manuscript | ||
| Virtual Presentation | Click here to watch in the Virtual Symposium | ||
| Abstract | Cloud computing platforms have created the possibility for computationally limited users to delegate demanding tasks to strong but untrusted servers. Verifiable computing algorithms help build trust in such interactions by enabling the server to provide a proof of correctness of his results which the user can check very efficiently. In this paper, we present a doubly-efficient interactive algorithm for verifiable polynomial evaluation. Unlike the mainstream literature on verifiable computing, the soundness of our algorithm is information-theoretic and cannot be broken by a computationally unbounded server. By relying on basic properties of error correcting codes, our algorithm enforces a dishonest server to provide false results to problems which become progressively easier to verify. After roughly $\log d$ rounds, the user can verify the response of the server against a look-up table that has been pre-computed during an initialization phase. For a polynomial of degree $d$, we achieve a user complexity of $O(d^{\epsilon})$, a server complexity of $O(d^{1+\epsilon})$, a round complexity of $O(\log d)$ and an initialization complexity of $O(d^{1+\epsilon})$. | ||
Plan Ahead
2021 IEEE International Symposium on Information Theory
11-16 July 2021 | Melbourne, Victoria, Australia
