A Survey of Interactive Verifiable Computing: Utilizing Randomness in Low-Degree Polynomials

Angold Wang

Paper 2025/008

A Survey of Interactive Verifiable Computing: Utilizing Randomness in Low-Degree Polynomials

Angold Wang

, Hong Kong Baptist University

Abstract

This survey provides a comprehensive examination of verifiable computing, tracing its evolution from foundational complexity theory to modern zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARKs). We explore key developments in interactive proof systems, knowledge complexity, and the application of low-degree polynomials in error detection and verification protocols. The survey delves into essential mathematical frameworks such as the Cook-Levin Theorem, the sum-check protocol, and the GKR protocol, highlighting their roles in enhancing verification efficiency and soundness. By systematically addressing the limitations of traditional NP-based proof systems and then introducing advanced interactive proof mechanisms to overcome them, this work offers an accessible step-by-step introduction for newcomers while providing detailed mathematical analyses for researchers. Ultimately, we synthesize these concepts to elucidate the GKR protocol, which serves as a foundation for contemporary verifiable computing models. This survey not only reviews the historical and theoretical advancements in verifiable computing over the past three decades but also lays the groundwork for understanding recent innovations in the field.

Note: Title: A Survey of Interactive Verifiable Computing: Utilizing Randomness in Low-Degree Polynomials Keywords: Zero-Knowledge, Interactive Proof Systems, Verifiable Computing, Low-Degree Polynomials, Sum-Check Protocol, GKR Protocol, Complexity Theory, Cryptography

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint.
Keywords: Interactive Proof Systems Verifiable Computing Sum-Check Protocol GKR Protocol Complexity Theory
Contact author(s): angold @ life hkbu edu hk
History: 2025-01-09: last of 2 revisions; 2025-01-02: received; See all versions
Short URL: https://ia.cr/2025/008
License: CC BY

BibTeX

@misc{cryptoeprint:2025/008,
      author = {Angold Wang},
      title = {A Survey of Interactive Verifiable Computing: Utilizing Randomness in Low-Degree Polynomials},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/008},
      year = {2025},
      url = {https://eprint.iacr.org/2025/008}
}