Efficient Non-Interactive Verifiable Outsourced Computation for Arbitrary Functions

Abstract. Non-interactive verifiable outsourced computation enables a computationally weak client to outsource the computation of a function f on input x to a more powerful but untrusted server, who will return the result of the function evaluation as well as a proof that the computation is performed correctly. A basic requirement of a verifiable outsourced computation scheme is that the client should invest less time in prepar-ing the inputs and verifying the proof than computing the function by himself. One of the best solutions of such non-interactive schemes are based on Yao’s garble circuit and full homomorphic encryption, which leads to invest poly(T) running time in offline stage and poly(logT) time in online stage of the client, where T is the time complexity to compute f. In this paper, we’ll present a scheme which does not need to use garble circuit, but to use a very simple technique to confuse the function we are going to compute, and only invests poly(logT) running time in the offline stage