Can I read Block Programs: Improving Efficiency of Verifiable Computation for Circuits with Repeated Substructures on EtoBox?

Block Programs: Improving Efficiency of Verifiable Computation for Circuits with Repeated Substructures by Gang Xu; George Amariucai; Yong Guan is a scholarly article available to read on EtoBox.

What is Block Programs: Improving Efficiency of Verifiable Computation for Circuits with Repeated Substructures about?

In the cloud computing paradigm, clients outsource computation to professional service providers. However, service providers may be error-prone or otherwise not entirely trustworthy, and therefore oftentimes the returned results need to be thoroughly verified. As such, the problem of verifiable computation has been motivating a rapidly-growing body of research, yielding increasingly-efficient systems, which currently achieve nearly-practical verifiable computation. Most recent solutions firstly transform the computation task into an arithmetic circuit, and then based on this circuit they design a verification protocol using argument systems. In this paper we focus on the verification protocol after the circuit generation. We notice the state of the art involve a considerable cost, including the verifier's amortized cost, (i.e., the cost that needs to be amortized over a large number of work instances), and the prover's cost of proof generation. The most efficient argument systems still incur an amortized cost that is linear in the size of the circuit. In this paper, we show that verifiable computation can be made more efficient by taking advantage of computations with corresponding

Author

Gang Xu; George Amariucai; Yong Guan

Publisher

ACM

Published

2015

Language

EN