Verifiable Computation and Succinct Arguments for NP
Dario Fiore · 2022
The simultaneous achievement of security and efficiency makes Verifiable computation (VC) an intriguing notion that attracts interest from both the theory and the practice sides of computer science. This chapter presents the definition of VC, and describes a construction of VC for computations expressible as polynomial-size arithmetic circuits. It focuses on showing how to construct a VC scheme for an important class of computations that are arithmetic circuits of polynomial size. The chapter presents the notion of a succinct non-interactive argument (SNARG) and shows how any SNARG for NP can be used to build a VC for polynomial time functions. It presents a construction that follows a modular approach based on combining two objects: an information theoretic proof system working in an ideal abstract model and a cryptographic component that turns the information-theoretic proof into an efficient computationally sound argument.