Accession Number : AD1024615


Title :   Toward Practical Verification of Outsourced Computations Using Probabilistically Checkable Proofs (PCPs)


Descriptive Note : Technical Report


Corporate Author : University of Texas at Austin Austin United States


Personal Author(s) : Setty,Srinath ; Blumberg,Andrew ; Walfish,Michael


Full Text : https://apps.dtic.mil/dtic/tr/fulltext/u2/1024615.pdf


Report Date : 12 Jul 2010


Pagination or Media Count : 11


Abstract : This paper describes preliminary results and outlines the plan of attack for an on-going project to develop a practical system for verifying outsourced computations. We want a client to be able to describe a computation to a server, get back a purported output and some auxiliary information, and use that auxiliary information to verify that the output is correct. For outsourcing to be worthwhile, the verification process should be substantially more efficient than simply executing the computation. Our approach to this problem is to exploit the theory of probabilistically checkable proofs (PCPs). Specifically, our project seeks to build a bridge between the theory and an implementable system. We describe a protocol for outsourced computation that includes algorithmic refinements of the PCP protocol and end-to-end instantiation of the necessary steps (e.g., compilation to a form suitable for application of the PCP theorem). Although we are in the process of implementing the protocol and do not have experimental results, we present a detailed analysis that provides cause for optimism: our cycle and memory usage costs strongly suggest that our system will be useful. We focus on the example of matrix multiplication, where we show that for large matrices, our method achieves enormous savings for the client and requires feasible amounts of bandwidth.


Descriptors :   probability , computer programming , computations , outsourcing , CLIENT SERVER SYSTEMS , polynomials , algorithms


Subject Categories : Statistics and Probability
      Numerical Mathematics
      Computer Programming and Software


Distribution Statement : APPROVED FOR PUBLIC RELEASE