Interactive Verifiable Polynomial Evaluation

Saeid Sahraei, Mohammad Ali Maddah-Ali, Salman Avestimehr

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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 logd 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^\varepsilon , a server complexity of O(d^{1 + \varepsilon )} \right), a round complexity of O(logd) and an initialization complexity of O(d^{1 + \varepsilon )} \right).

Original languageEnglish (US)
Title of host publication2020 IEEE International Symposium on Information Theory, ISIT 2020 - Proceedings
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages6
ISBN (Electronic)9781728164328
StatePublished - Jun 2020
Externally publishedYes
Event2020 IEEE International Symposium on Information Theory, ISIT 2020 - Los Angeles, United States
Duration: Jul 21 2020Jul 26 2020

Publication series

NameIEEE International Symposium on Information Theory - Proceedings
ISSN (Print)2157-8095


Conference2020 IEEE International Symposium on Information Theory, ISIT 2020
Country/TerritoryUnited States
CityLos Angeles

Bibliographical note

Publisher Copyright:
© 2020 IEEE.


Dive into the research topics of 'Interactive Verifiable Polynomial Evaluation'. Together they form a unique fingerprint.

Cite this