On Black-Box Verifiable Outsourcing

We study verifiable outsourcing of computation in a model where the verifier has black-box access to the function being computed. We introduce the problem of oracle-aided batch verification of computation (OBVC) for a function class F. This allows a verifier to efficiently verify the correctness of any f is an element of F evaluated on a batch of n instances x(1),..., x(n), while only making lambda calls to an oracle for f (along with O(n lambda) calls to low-complexity helper oracles), for security parameter lambda. We obtain the following positive and negative results: - We build OBVC protocols for the class of all functions that admit random-self-reductions. Some of our protocols rely on homomorphic encryption schemes. - We show that there cannot exist OBVC schemes for the class of all functions mapping lambda-bit inputs to lambda-bit outputs, for any n = poly(lambda).(1)((1) The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/.)