Welcome to the resource topic for 2023/1466
Title:
On Black-Box Verifiable Outsourcing
Authors: Amit Agarwal, Navid Alamati, Dakshita Khurana, Srinivasan Raghuraman, Peter Rindal
Abstract: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).
ePrint: https://eprint.iacr.org/2023/1466
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .