nach oben

Erschienen in:

2023 | OriginalPaper | Buchkapitel

On Black-Box Verifiable Outsourcing

verfasst von : Amit Agarwal, Navid Alamati, Dakshita Khurana, Srinivasan Raghuraman, Peter Rindal

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config

KI-gestützte Suche

Aus

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:

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 \(\lambda \)-bit inputs to \(\lambda \)-bit outputs, for any \(n = \textsf{poly} (\lambda )\).\(^{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/.)

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Vorheriges Kapitel Rogue-Instance Security for Batch Knowledge Proofs

Nächstes Kapitel Counting Unpredictable Bits: A Simple PRG from One-Way Functions

We use \(\frac{{\lambda }}{2K}\) as opposed to \(\frac{{\lambda }}{2}\) as this is what we need in the setting of K provers to make the rest of the analysis work out.

For syntactic simplicity, we only consider functions with a single bit output. The generalization to functions with arbitrary output length can be done by splitting a multi-bit output function into multiple functions with single bit output.

In cases where \(T_f(\ell )\) is not known, due to circuit lower bound barriers, we can fix \(T_f(\ell )\) to be the best known time complexity for computing f on (worst-case) inputs of size \(\ell \). For example, if f is the matrix multiplication function of two \(\ell \times \ell \) bit matrices, then we can set \(T_f(\ell ) = \ell ^{2.3728596}\) for inputs of length \(2{\ell }^2\) (encoding two \(\ell \times \ell \) sized bit-matrix as a bit-string) based on the fastest known matrix multiplication algorithm [1].

Alman, J., Williams, V.V.: A refined laser method and faster matrix multiplication. In: Proceedings of the 2021 ACM-SIAM Symposium on Discrete Algorithms (SODA), pp. 522–539. SIAM (2021)

Applebaum, B., Ishai, Y., Kushilevitz, E.: From secrecy to soundness: efficient verification via secure computation. In: Abramsky, S., Gavoille, C., Kirchner, C., Meyer auf der Heide, F., Spirakis, P.G. (eds.) ICALP 2010. LNCS, vol. 6198, pp. 152–163. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14165-2_14CrossRef

Ar, S., Blum, M., Codenotti, B., Gemmell, P.: Checking approximate computations over the reals. In: Proceedings of the Twenty-Fifth Annual ACM Symposium on Theory of Computing, pp. 786–795 (1993)

Beaver, D., Feigenbaum, J., Kilian, J., Rogaway, P.: Locally random reductions: improvements and applications. J. Cryptol. 10(1), 17–36 (1997)MathSciNetCrossRefMATH

Bellare, M., Garay, J.A., Rabin, T.: Batch verification with applications to cryptography and checking. In: Lucchesi, C.L., Moura, A.V. (eds.) LATIN 1998. LNCS, vol. 1380, pp. 170–191. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0054320CrossRef

Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: Proceedings of the 1st ACM Conference on Computer and Communications Security, pp. 62–73 (1993)

Blum, M., Luby, M., Rubinfeld, R.: Self-testing/correcting with applications to numerical problems. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 73–83 (1990)

Blum, M., Luby, M., Rubinfeld, R.: Program result checking against adaptive programs. In: Distributed Computing and Cryptography: Proceedings of a DIMACS Workshop, October 4–6, 1989, vol. 2, p. 107. American Mathematical Soc. (1991)

Brakerski, Z., Holmgren, J., Kalai, Y.: Non-interactive ram and batch NP delegation from any PIR. Cryptology ePrint Archive (2016)

10.

Brakerski, Z., Holmgren, J., Kalai, Y.: Non-interactive delegation and batch NP verification from standard computational assumptions. In: Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing, pp. 474–482 (2017)

11.

Brakerski, Z., Vaikuntanathan, V.: Efficient fully homomorphic encryption from (standard) LWE. SIAM J. Comput. 43(2), 831–871 (2014)MathSciNetCrossRefMATH

12.

Choudhuri, A.R., Jain, A., Jin, Z.: Non-interactive batch arguments for NP from standard assumptions. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12828, pp. 394–423. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-84259-8_14CrossRef

13.

Choudhuri, A.R., Jain, A., Jin, Z.: Snargs for \(\cal{P}\) from LWE. In: 62nd IEEE Annual Symposium on Foundations of Computer Science, FOCS 2021, Denver, CO, USA, February 7–10, 2022. pp. 68–79. IEEE (2021). https://doi.org/10.1109/FOCS52979.2021.00016

14.

Chung, K.-M., Kalai, Y., Vadhan, S.: Improved delegation of computation using fully homomorphic encryption. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 483–501. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_26CrossRef

15.

Cleve, R., Luby, M.: A note on self-testing/correcting methods for trigonometric functions. International Computer Science Inst. (1990)

16.

Coretti, S., Dodis, Y., Guo, S., Steinberger, J.: Random oracles and non-uniformity. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 227–258. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78381-9_9CrossRef

17.

Dodis, Y., Guo, S., Katz, J.: Fixing cracks in the concrete: random oracles with auxiliary input, revisited. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 473–495. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56614-6_16CrossRef

18.

Gemmell, P., Lipton, R., Rubinfeld, R., Sudan, M., Wigderson, A.: Self-testing/Correcting for polynomials and for approximate functions. In: STOC, vol. 91, pp. 32–42. Citeseer (1991)

19.

Gennaro, R., Gentry, C., Parno, B.: Non-interactive verifiable computing: outsourcing computation to untrusted workers. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 465–482. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-14623-7_25CrossRef

20.

Hoeffding, W.: Probability inequalities for sums of bounded random variables. The Collected Works of Wassily Hoeffding, pp. 409–426 (1994)

21.

Hulett, J., Jawale, R., Khurana, D., Srinivasan, A.: SNARGs for P from sub-exponential DDH and QR. In: Dunkelman, O., Dziembowski, S. (eds.) Advances in Cryptology - EUROCRYPT 2022, Part II. Lecture Notes in Computer Science, vol. 13276, pp. 520–549. Springer, Heidelberg, Germany, Trondheim, Norway (May 30 - Jun 3, 2022). https://doi.org/10.1007/978-3-031-07085-3_18

22.

Jawale, R., Kalai, Y.T., Khurana, D., Zhang, R.Y.: SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. In: Khuller, S., Williams, V.V. (eds.) STOC ’21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, Virtual Event, Italy, June 21–25, 2021, pp. 708–721. ACM (2021). https://doi.org/10.1145/3406325.3451055

23.

Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pp. 485–494 (2014)

24.

Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing, pp. 723–732 (1992)

25.

Lipton, R.: New directions in testing. Distrib. Comput. Crypt. 2, 191–202 (1991)MathSciNetMATH

26.

Micali, S.: Computationally sound proofs. SIAM J. Comput. 30(4), 1253–1298 (2000)MathSciNetCrossRefMATH

27.

Rubinfeld, R.: Batch checking with applications to linear functions. Inf. Process. Lett. 42(2), 77–80 (1992)MathSciNetCrossRefMATH

28.

Unruh, D.: Random oracles and auxiliary input. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 205–223. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_12CrossRef

29.

Waters, B., Wu, D.J.: Batch arguments for np and more from standard bilinear group assumptions. In: Annual International Cryptology Conference, pp. 433–463. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-15979-4_15

Titel: On Black-Box Verifiable Outsourcing
verfasst von: Amit Agarwal
Navid Alamati
Dakshita Khurana
Srinivasan Raghuraman
Peter Rindal
Verlag: Springer Nature Switzerland
Buch: Theory of Cryptography
Print ISBN: 978-3-031-48614-2

Electronic ISBN: 978-3-031-48615-9

Copyright-Jahr: 2023
DOI: https://doi.org/10.1007/978-3-031-48615-9_6

Springer Professional

Abstract

Bitte loggen Sie sich ein, um Zugang zu Ihrer Lizenz zu erhalten.

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner