Paper 2023/1466
On Black-Box Verifiable Outsourcing
, University of Illinois Urbana-Champaign, USA, Visa Research, USA, University of Illinois Urbana-Champaign, USA, Visa Research and MIT, USA, Visa Research, USAAbstract
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)$.
Note: Full version of the TCC 2023 paper.
Metadata
- Available format(s)
-
PDF
- Category
- Foundations
- Publication info
- A major revision of an IACR publication in TCC 2023
- Keywords
- verifiable computationblackbox verificationrandom self reduction
- Contact author(s)
-
amita2 @ illinois edu
nalamati @ visa com
dakshita @ illinois edu
srini131293 @ gmail com
perindal @ visa com - History
- 2023-09-27: approved
- 2023-09-24: received
- See all versions
- Short URL
- https://ia.cr/2023/1466
- License
-
CC BY-NC
BibTeX
@misc{cryptoeprint:2023/1466,
author = {Amit Agarwal and Navid Alamati and Dakshita Khurana and Srinivasan Raghuraman and Peter Rindal},
title = {On Black-Box Verifiable Outsourcing},
howpublished = {Cryptology ePrint Archive, Paper 2023/1466},
year = {2023},
note = {\url{https://eprint.iacr.org/2023/1466}},
url = {https://eprint.iacr.org/2023/1466}
}
