CryptoDB
On Black-Box Verifiable Outsourcing
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | TCC 2023 |
| Abstract: | We study the problem of verifiably outsourcing 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 \in 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), where \lambda denotes a security parameter. We obtain the following positive and negative results: 1. We build OBVC protocols for the class F 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 F of all functions mapping \lambda-bit inputs to \lambda-bit outputs, for any n = \poly(\lambda). |
BibTeX
@inproceedings{tcc-2023-33638,
title={On Black-Box Verifiable Outsourcing},
publisher={Springer-Verlag},
author={Amit Agarwal and Navid Alamati and Dakshita Khurana and Srinivasan Raghuraman and Peter Rindal},
year=2023
}