On Black-Box Verifiable Outsourcing

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

doi:10.1007/978-3-031-48615-9_6

On Black-Box Verifiable Outsourcing

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

Siebel School of Computing and Data Science

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

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 F. This allows a verifier to efficiently verify the correctness of any f∈ F evaluated on a batch of n instances x₁, …, x_n, while only making λ calls to an oracle for f (along with O(nλ) calls to low-complexity helper oracles), for security parameter λ. We obtain the following positive and negative results: We build OBVC protocols for the class of all functions that admit random-self-reductions. Some of our protocols rely on homomorphic encryption schemes.We show that there cannot exist OBVC schemes for the class of all functions mapping λ -bit inputs to λ -bit outputs, for any n= poly(λ).¹ (¹ The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/.)

Original language	English (US)
Title of host publication	Theory of Cryptography - 21st International Conference, TCC 2023, Proceedings
Editors	Guy Rothblum, Hoeteck Wee
Publisher	Springer
Pages	158-187
Number of pages	30
ISBN (Print)	9783031486142
DOIs	https://doi.org/10.1007/978-3-031-48615-9_6
State	Published - 2023
Event	21st International conference on Theory of Cryptography Conference, TCC 2023 - Taipei, Taiwan, Province of China Duration: Nov 29 2023 → Dec 2 2023

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	14369 LNCS
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	21st International conference on Theory of Cryptography Conference, TCC 2023
Country/Territory	Taiwan, Province of China
City	Taipei
Period	11/29/23 → 12/2/23

ASJC Scopus subject areas

Theoretical Computer Science
General Computer Science

Online availability

10.1007/978-3-031-48615-9_6

Library availability

Discover UIUC Full Text

Cite this

Agarwal, A., Alamati, N., Khurana, D., Raghuraman, S., & Rindal, P. (2023). On Black-Box Verifiable Outsourcing. In G. Rothblum, & H. Wee (Eds.), Theory of Cryptography - 21st International Conference, TCC 2023, Proceedings (pp. 158-187). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14369 LNCS). Springer. https://doi.org/10.1007/978-3-031-48615-9_6

On Black-Box Verifiable Outsourcing. / Agarwal, Amit; Alamati, Navid; Khurana, Dakshita et al.
Theory of Cryptography - 21st International Conference, TCC 2023, Proceedings. ed. / Guy Rothblum; Hoeteck Wee. Springer, 2023. p. 158-187 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 14369 LNCS).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution

Agarwal, A, Alamati, N, Khurana, D, Raghuraman, S & Rindal, P 2023, On Black-Box Verifiable Outsourcing. in G Rothblum & H Wee (eds), Theory of Cryptography - 21st International Conference, TCC 2023, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 14369 LNCS, Springer, pp. 158-187, 21st International conference on Theory of Cryptography Conference, TCC 2023, Taipei, Taiwan, Province of China, 11/29/23. https://doi.org/10.1007/978-3-031-48615-9_6

Agarwal A, Alamati N, Khurana D, Raghuraman S, Rindal P. On Black-Box Verifiable Outsourcing. In Rothblum G, Wee H, editors, Theory of Cryptography - 21st International Conference, TCC 2023, Proceedings. Springer. 2023. p. 158-187. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-48615-9_6

Agarwal, Amit ; Alamati, Navid ; Khurana, Dakshita et al. / On Black-Box Verifiable Outsourcing. Theory of Cryptography - 21st International Conference, TCC 2023, Proceedings. editor / Guy Rothblum ; Hoeteck Wee. Springer, 2023. pp. 158-187 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{c60c132e5368433c81b3f4ea9f54240a,

title = "On Black-Box Verifiable Outsourcing",

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 F. This allows a verifier to efficiently verify the correctness of any f∈ F evaluated on a batch of n instances x1, …, xn, while only making λ calls to an oracle for f (along with O(nλ) calls to low-complexity helper oracles), for security parameter λ. We obtain the following positive and negative results: We build OBVC protocols for the class of all functions that admit random-self-reductions. Some of our protocols rely on homomorphic encryption schemes.We show that there cannot exist OBVC schemes for the class of all functions mapping λ -bit inputs to λ -bit outputs, for any n= poly(λ).1 (1 The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/.)",

author = "Amit Agarwal and Navid Alamati and Dakshita Khurana and Srinivasan Raghuraman and Peter Rindal",

note = "Publisher Copyright: {\textcopyright} 2023, International Association for Cryptologic Research.; 21st International conference on Theory of Cryptography Conference, TCC 2023 ; Conference date: 29-11-2023 Through 02-12-2023",

year = "2023",

doi = "10.1007/978-3-031-48615-9_6",

language = "English (US)",

isbn = "9783031486142",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "158--187",

editor = "Guy Rothblum and Hoeteck Wee",

booktitle = "Theory of Cryptography - 21st International Conference, TCC 2023, Proceedings",

address = "Germany",

}

TY - GEN

T1 - On Black-Box Verifiable Outsourcing

AU - Agarwal, Amit

AU - Alamati, Navid

AU - Khurana, Dakshita

AU - Raghuraman, Srinivasan

AU - Rindal, Peter

PY - 2023

Y1 - 2023

N2 - 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 F. This allows a verifier to efficiently verify the correctness of any f∈ F evaluated on a batch of n instances x1, …, xn, while only making λ calls to an oracle for f (along with O(nλ) calls to low-complexity helper oracles), for security parameter λ. We obtain the following positive and negative results: We build OBVC protocols for the class of all functions that admit random-self-reductions. Some of our protocols rely on homomorphic encryption schemes.We show that there cannot exist OBVC schemes for the class of all functions mapping λ -bit inputs to λ -bit outputs, for any n= poly(λ).1 (1 The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/.)

AB - 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 F. This allows a verifier to efficiently verify the correctness of any f∈ F evaluated on a batch of n instances x1, …, xn, while only making λ calls to an oracle for f (along with O(nλ) calls to low-complexity helper oracles), for security parameter λ. We obtain the following positive and negative results: We build OBVC protocols for the class of all functions that admit random-self-reductions. Some of our protocols rely on homomorphic encryption schemes.We show that there cannot exist OBVC schemes for the class of all functions mapping λ -bit inputs to λ -bit outputs, for any n= poly(λ).1 (1 The authors grant IACR a non-exclusive and irrevocable license to distribute the article under the https://creativecommons.org/licenses/by-nc/3.0/.)

UR - http://www.scopus.com/inward/record.url?scp=85178600625&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=85178600625&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-48615-9_6

DO - 10.1007/978-3-031-48615-9_6

M3 - Conference contribution

AN - SCOPUS:85178600625

SN - 9783031486142

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 158

EP - 187

BT - Theory of Cryptography - 21st International Conference, TCC 2023, Proceedings

A2 - Rothblum, Guy

A2 - Wee, Hoeteck

PB - Springer

T2 - 21st International conference on Theory of Cryptography Conference, TCC 2023

Y2 - 29 November 2023 through 2 December 2023

ER -

On Black-Box Verifiable Outsourcing

Abstract

Publication series

Conference

ASJC Scopus subject areas

Online availability

Library availability

Related links

Fingerprint

Cite this