Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
ATZ-Fachkongress

Chassis.tech plus 2024


4 Kongresse in einer Veranstaltung

Treffen Sie in München die Fachleute von Chassis, Lenkung, Bremsen sowie Reifen/Räder.
Erweiterte Suche
Anmelden
nach oben
Erschienen in:
Beyond MPC-in-the-Head: Black-Box Constructions of Short Zero-Knowledge Proofs Kapitel lesen Erstes Kapitel lesen

2023 | OriginalPaper | Buchkapitel

Distributed-Prover Interactive Proofs

verfasst von : Sourav Das, Rex Fernando, Ilan Komargodski, Elaine Shi, Pratik Soni

Erschienen in: Theory of Cryptography

Verlag: Springer Nature Switzerland

Einloggen

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

search-config
loading …

Abstract

Interactive proof systems enable a verifier with limited resources to decide an intractable language (or compute a hard function) by communicating with a powerful but untrusted prover. Such systems guarantee soundness: the prover can only convince the verifier of true statements. This is a central notion in computer science with far-reaching implications. One key drawback of the classical model is that the data on which the prover operates must be held by a single machine.
In this work, we initiate the study of distributed-prover interactive proofs (dpIPs): an untrusted cluster of machines, acting as a distributed prover, interacts with a single verifier. The machines in the cluster jointly store and operate on a massive data-set that no single machine can store. The goal is for the machines in the cluster to convince the verifier of the validity of some statement about its data-set. We formalize the communication and space constraints via the massively parallel computation (MPC) model, a widely accepted analytical framework capturing the computational power of massive data-centers.
Our main result is a compiler that generically augments any verification algorithm in the MPC model with a (computational) soundness guarantee. Concretely, for any language L for which there is an MPC algorithm verifying whether \(x \in L\), we design a new MPC protocol capable of convincing a verifier of the validity of \(x \in L\) and where if \(x\not \in L\), the verifier rejects with overwhelming probability. The new protocol requires only slightly more rounds, i.e., a \(\textsf{poly}(\log N)\) blowup, and a slightly bigger memory per machine, i.e., \(\textsf{poly}(\lambda )\) blowup, where N is the total size of the dataset and \(\lambda \) is a security parameter independent of N.
En route, we introduce distributed-prover interactive oracle proofs (dpIOPs), a natural adaptation of the (by now classical) IOP model to the distributed prover setting. We design a dpIOP for verification algorithms in the MPC model and then translate them to “plain model” dpIPs via an adaptation of existing polynomial commitment schemes into the distributed prover setting.

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 Locally Verifiable Distributed SNARGs
Nächstes Kapitel Rogue-Instance Security for Batch Knowledge Proofs
Literatur
1.
Kook Jin Ahn and Sudipto Guha: Access to data and number of iterations: dual primal algorithms for maximum matching under resource constraints. ACM Trans. Parallel Comput. (TOPC) 4(4), 17 (2018)
2.
Andoni, A., Nikolov, A., Onak, K., Yaroslavtsev, G.: Parallel algorithms for geometric graph problems. In: STOC 2014 (2014)
3.
Andoni, A., Stein, C., Zhong, P.: Log diameter rounds algorithms for \(2 \)-vertex and \(2 \)-edge connectivity. arXiv preprint arXiv:​1905.​00850 (2019)
4.
Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification and hardness of approximation problems. In: 33rd Annual Symposium on Foundations of Computer Science, FOCS, pp. 14–23 (1992)
5.
Arun, A., Ganesh, C., Lokam, S.V., Mopuri, T., Sridhar, S.: Dew: a transparent constant-sized polynomial commitment scheme. In: Public Key Cryptography, pp. 542–571 (2023)
6.
Assadi, S.: Simple round compression for parallel vertex cover. CoRR, abs/1709.04599 (2017)
7.
Assadi, S., Bateni, M.H., Bernstein, A., Mirrokni, V., Stein, C.: Coresets meet EDCS: algorithms for matching and vertex cover on massive graphs. arXiv preprint arXiv:​1711.​03076 (2017)
8.
Assadi, S., Khanna, S.: Randomized composable coresets for matching and vertex cover. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 3–12. ACM (2017)
9.
Assadi, S., Sun, X., Weinstein, O.: Massively parallel algorithms for finding well-connected components in sparse graphs. CoRR, abs/1805.02974 (2018)
10.
Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC, pp. 21–31 (1991)
11.
Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complex. 1, 3–40 (1991)CrossRefMATH
12.
Bahmani, B., Kumar, R., Vassilvitskii, S.: Densest subgraph in streaming and MapReduce. Proc. VLDB Endow. 5(5), 454–465 (2012)CrossRef
13.
Bahmani, B., Moseley, B., Vattani, A., Kumar, R., Vassilvitskii, S.: Scalable k-means++. Proc. VLDB Endow. 5(7), 622–633 (2012)CrossRef
14.
Bateni, M.H., Bhaskara, A., Lattanzi, S., Mirrokni, V.: Distributed balanced clustering via mapping coresets. In: Advances in Neural Information Processing Systems, pp. 2591–2599 (2014)
15.
Behnezhad, S., Derakhshan, M., Hajiaghayi, M.T., Karp, R.M.: Massively parallel symmetry breaking on sparse graphs: MIS and maximal matching. CoRR, abs/1807.06701 (2018)
16.
Behnezhad, S., Hajiaghayi, M.T., Harris, D.G.: Exponentially faster massively parallel maximal matching. arXiv preprint arXiv:​1901.​03744 (2019)
17.
Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Fast reed-Solomon interactive oracle proofs of proximity. In: 45th International Colloquium on Automata, Languages, and Programming (ICALP), pp. 14:1–14:17. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany (2018)
18.
19.
Ben-Sasson, E., Goldberg, L., Kopparty, S., Saraf, S.: DEEP-FRI: sampling outside the box improves soundness, pp. 5:1–5:32 (2020)
20.
Bick, A., Kol, G., Oshman, R.: Distributed zero-knowledge proofs over networks. In: SODA, pp. 2426–2458 (2022)
21.
Block, A.R., Holmgren, J., Rosen, A., Rothblum, R.D., Soni, P.: Public-coin zero-knowledge arguments with (almost) minimal time and space overheads. In: Theory of Cryptography, pp. 168–197 (2020)
22.
23.
Blumberg, A.J., Thaler, J., Vu, V., Walfish, M.: Verifiable computation using multiple provers. IACR Cryptol. ePrint Arch., p. 846 (2014)
24.
25.
26.
Brandt, S., Fischer, M., Uitto, J.: Matching and MIS for uniformly sparse graphs in the low-memory MPC model. CoRR, abs/1807.05374 (2018)
27.
28.
Chang, Y.-J., Fischer, M., Ghaffari, M., Uitto, J., Zheng, Y.: The complexity of (\(\Delta \)+1) coloring incongested clique, massively parallel computation, and centralized local computation. arXiv preprint arXiv:​1808.​08419 (2018)
29.
30.
Chung, K.-M., Ho, K.-Y., Sun, X.: On the hardness of massively parallel computation. In: 32nd ACM Symposium on Parallelism in Algorithms and Architectures, SPAA, pp. 153–162 (2020)
31.
Czumaj, A., Ła̧cki, J., Ma̧dry, A., Mitrović, S., Onak, K., Sankowski, P.: Round compression for parallel matching algorithms. In: STOC (2018)
32.
da Ponte Barbosa, R., Ene, A., Nguyen, H.L., Ward, J.: A new framework for distributed submodular maximization. In: FOCS, pp. 645–654 (2016)
33.
Ene, A., Im, S., Moseley, B.: Fast clustering using MapReduce. In: Proceedings of the 17th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining, pp. 681–689. ACM (2011)
34.
Ene, A., Nguyen, H.: Random coordinate descent methods for minimizing decomposable submodular functions. In: International Conference on Machine Learning, pp. 787–795 (2015)
35.
Fernando, R., Gelles, Y., Komargodski, I., Shi, E.: Maliciously secure massively parallel computation for all-but-one corruptions. In: Dodis, Y., Shrimpton, T. (eds.) Advances in Cryptology. CRYPTO 2022. LNCS, vol. 13507, pp. 688–718. Springer, Cham (2022). https://​doi.​org/​10.​1007/​978-3-031-15802-5_​24
36.
Fernando, R., Komargodski, I., Liu, Y., Shi, E.: Secure massively parallel computation for dishonest majority. In: Theory of Cryptography - 18th International Conference, TCC, pp. 379–409 (2020)
37.
Gabizon, A., Williamson, Z.J., Ciobotaru, O.: Plonk: permutations over Lagrange-bases for oecumenical noninteractive arguments of knowledge. Cryptology ePrint Archive (2019)
38.
Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC, pp. 99–108 (2011)
39.
Ghaffari, M., Lattanzi, S., Mitrović, S.: Improved parallel algorithms for density-based network clustering. In: International Conference on Machine Learning, pp. 2201–2210 (2019)
40.
Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691–729 (1991)MathSciNetCrossRefMATH
41.
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186–208 (1989)MathSciNetCrossRefMATH
42.
Karloff, H.J., Suri, S., Vassilvitskii, S.: A model of computation for MapReduce. In: Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA, pp. 938–948 (2010)
43.
44.
Kattis, A.A., Panarin, K., Vlasov, A.: Redshift: transparent snarks from list polynomial commitments. In: CCS, pp. 1725–1737 (2022)
45.
Kol, G., Oshman, R., Saxena, R.R.: Interactive distributed proofs. In: PODC, pp. 255–264 (2018)
46.
Kumar, R., Moseley, B., Vassilvitskii, S., Vattani, A.: Fast greedy algorithms in MapReduce and streaming. TOPC. 2(3), 1–22 (2015)CrossRef
47.
Lee, J.: Dory: efficient, transparent arguments for generalised inner products and polynomial commitments. In: Theory of Cryptography, pp. 1–34 (2021)
48.
Lindell: Parallel coin-tossing and constant-round secure two-party computation. J. Cryptol. 16, 143–184 (2003)
49.
50.
Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: SODA, pp. 1096–115 (2020)
51.
Ozdemir, A., Boneh, D.: Experimenting with collaborative ZK-snarks: zero-knowledge proofs for distributed secrets. In: USENIX, pp. 4291–4308 (2022)
52.
Papamanthou, C., Shi, E., Tamassia, R.: Signatures of correct computation. In: Theory of Cryptography, pp. 222–242 (2013)
53.
Rivest, R.L., Shamir, A., Adleman, L.: A method for obtaining digital signatures and public-key cryptosystems. Commun. ACM. 21(2), 120–126 (1978)MathSciNetCrossRefMATH
54.
Roughgarden, T., Vassilvitskii, S., Wang, J.R.: Shuffles and circuits (on lower bounds for modern parallel computation). J. ACM 65(6), 1–24 (2018)MathSciNetCrossRefMATH
55.
Setty, S., Lee, J.: Quarks: quadruple-efficient transparent Zksnarks. Cryptology ePrint Archive, Paper 2020/1275 (2020)
56.
Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient Zksnarks without trusted setup. In: S&P, pp. 926–943 (2018)
57.
58.
Wu, H., Zheng, W., Chiesa, A., Popa, R.A., Stoica, I.: DIZK: a distributed zero knowledge proof system. In: USENIX, pp. 675–692 (2018)
59.
Zhang, J., Xie, T., Zhang, Y., Song, D.: Transparent polynomial delegation and its applications to zero knowledge proof. In: S&P, pp. 859–876 (2020)
Metadaten
Titel
Distributed-Prover Interactive Proofs
verfasst von
Sourav Das
Rex Fernando
Ilan Komargodski
Elaine Shi
Pratik Soni
Copyright-Jahr
2023
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_4

Premium Partner

    Bildnachweise