International Association
for Cryptologic Research

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 $\mathcal{F}$. This allows a verifier to efficiently verify the correctness of any $f \in \mathcal{F}$ evaluated on a batch of $n$ instances $x_1, \ldots, 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:

1.) We build OBVC protocols for the class of all functions that admit random-self-reductions. Some of our protocols rely on homomorphic encryption schemes.

2.) 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 = \mathsf{poly}(\lambda)$.