On Black-Box Verifiable Outsourcing

Amit Agarwal; Navid Alamati; Dakshita Khurana; Srinivasan Raghuraman; Peter Rindal

Paper 2023/1466

On Black-Box Verifiable Outsourcing

Amit Agarwal

, University of Illinois Urbana-Champaign, USA

Navid Alamati

, Visa Research, USA

Dakshita Khurana

, University of Illinois Urbana-Champaign, USA

Srinivasan Raghuraman

, Visa Research and MIT, USA

Peter Rindal

, Visa Research, USA

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 . This allows a verifier to efficiently verify the correctness of any evaluated on a batch of instances , while only making calls to an oracle for (along with calls to low-complexity helper oracles), for security parameter . 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 -bit inputs to -bit outputs, for any .

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 computation blackbox verification random 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},
      url = {https://eprint.iacr.org/2023/1466}
}