Locally Verifiable Distributed SNARGs
Pages 65 - 90
Abstract
The field of distributed certification is concerned with certifying properties of distributed networks, where the communication topology of the network is represented as an arbitrary graph; each node of the graph is a separate processor, with its own internal state. To certify that the network satisfies a given property, a prover assigns each node of the network a certificate, and the nodes then communicate with one another and decide whether to accept or reject. We require soundness and completeness: the property holds if and only if there exists an assignment of certificates to the nodes that causes all nodes to accept. Our goal is to minimize the length of the certificates, as well as the communication between the nodes of the network. Distributed certification has been extensively studied in the distributed computing community, but it has so far only been studied in the information-theoretic setting, where the prover and the network nodes are computationally unbounded.
In this work we introduce and study computationally bounded distributed certification: we define locally verifiable distributeds ([inline-graphic not available: see fulltext]s), which are an analog of s for distributed networks, and are able to circumvent known hardness results for information-theoretic distributed certification by requiring both the prover and the verifier to be computationally efficient (namely, PPT algorithms).
We give two [inline-graphic not available: see fulltext] constructions: the first allows us to succinctly certify any network property in , using a global prover that can see the entire network; the second construction gives an efficient distributed prover, which succinctly certifies the execution of any efficient distributed algorithm. Our constructions rely on non-interactive batch arguments for (s) and on s, which have recently been shown to be constructible from standard cryptographic assumptions.
References
[1]
Aiello, W., Bhatt, S.N., Ostrovsky, R., Rajagopalan, S.: Fast verification of any remote procedure call: short witness-indistinguishable one-round proofs for np. In: Proceedings of the 27th International Colloquium on Automata, Languages and Programming, pp. 463–474 (2000)
[2]
Aldema Tshuva, E., Oshman, R.: Brief announcement: on polynomial-time local decision. In: Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing, pp. 48–50 (2022)
[3]
Awerbuch, B., Patt-Shamir, B., Varghese, G.: Self-stabilization by local checking and correction. In: Proceedings 32nd Annual Symposium of Foundations of Computer Science, pp. 268–277 (1991)
[4]
Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pp. 326–349 (2012)
[5]
Balliu A, D’Angelo G, Fraigniaud P, and Olivetti D What can be verified locally? J. Comput. Syst. Sci. 2018 97 106-120
[6]
Ben Shimon Y, Fischer O, and Oshman R Parter M Proof labeling schemes for reachability-related problems in directed graphs Structural Information and Communication Complexity 2022 Heidelberg Springer 21-41
[7]
Brakerski, Z., Holmgren, J., Kalai, Y.T.: 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)
[8]
Badrinarayanan, S., Kalai, Y.T., Khurana, D., Sahai, A., Wichs, D.: Succinct delegation for low-space non-deterministic computation. In: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing, pp. 709–721 (2018)
[9]
Bick, A., Kol, G., Oshman, R.: Distributed zero-knowledge proofs over networks. In: SODA, pp. 2426–2458. SIAM (2022)
[10]
Choudhuri, A.R., Garg, S., Jain, A., Jin, Z., Zhang, J.: Correlation intractability and SNARGs from sub-exponential DDH. Cryptology ePrint Archive (2022)
[11]
Choudhuri AR, Jain A, and Jin Z Malkin T and Peikert C Non-interactive batch arguments for NP from standard assumptions Advances in Cryptology – CRYPTO 2021 2021 Cham Springer 394-423
[12]
Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for P from LWE. In: 62nd IEEE Annual Symposium on Foundations of Computer Science (FOCS), pp. 68–79 (2021)
[13]
Di Crescenzo G and Lipmaa H Beckmann A, Dimitracopoulos C, and Löwe B Succinct NP proofs from an extractability assumption Logic and Theory of Algorithms 2008 Heidelberg Springer 175-185
[14]
Dwork, C., Langberg, M., Naor, M., Nissim, K., Reingold, O.: Succinct proofs for np and spooky interactions (2004). http://www.cs.bgu.ac.il/kobbi/papers/spooky_sub_crypto.pdf
[15]
Feuilloley, L., Bousquet, N., Pierron, T.: What can be certified compactly? compact local certification of MSO properties in tree-like graphs. In: PODC, pp. 131–140. ACM (2022)
[16]
Feuilloley, l.: Introduction to local certification. Disc. Math. Theor. Comput. Sci. 23(3) (2021)
[17]
Feuilloley L, Fraigniaud P, Hirvonen J, Paz A, and Perry M Redundancy in distributed proofs Distrib. Comput. 2021 34 2 113-132
[18]
Fraigniaud, P., Göös, M., Korman, A., Suomela, J.: What can be decided locally without identifiers? In: Proceedings of the 2013 ACM Symposium on Principles of Distributed Computing, pp. 157–165. ACM, New York (2013)
[19]
Fraigniaud P, Halldórsson MM, and Korman A Baldoni R, Flocchini P, and Binoy R On the impact of identifiers on local decision Principles of Distributed Systems 2012 Heidelberg Springer 224-238
[20]
Fraigniaud P, Korman A, and Peleg D Towards a complexity theory for local distributed computing J. ACM (JACM) 2013 60 5 1-26
[21]
Fraigniaud P, Montealegre P, Oshman R, Rapaport I, and Todinca I Censor-Hillel K and Flammini M On distributed merlin-arthur decision protocols Structural Information and Communication Complexity 2019 Cham Springer 230-245
[22]
Fraigniaud P, Montealegre P, Rapaport I, and Todinca I Parter M A meta-theorem for distributed certification Structural Information and Communication Complexity - 29th International Colloquium 2022 Heidelberg Springer 116-134
[23]
Fraigniaud P, Patt-Shamir B, and Perry M Randomized proof-labeling schemes Distrib. Comput. 2019 32 217-234
[24]
Groth J Abe M Short pairing-based non-interactive zero-knowledge arguments Advances in Cryptology - ASIACRYPT 2010 2010 Heidelberg Springer 321-340
[25]
Göös M and Suomela J Locally checkable proofs in distributed computing Theory Comput. 2016 12 1 1-33
[26]
Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Proceedings of the Forty-Third Annual ACM Symposium on Theory of Computing, pp. 99–108 (2011)
[27]
Holmgren, J., Rothblum, R.: Delegating computations with (almost) minimal time and space overhead. In: 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pp. 124–135. IEEE (2018)
[28]
Jawale, R., Kalai, Y.T., Khurana, D., Zhang, R.: SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. In: Proceedings of the 53rd Annual ACM SIGACT Symposium on Theory of Computing, pp. 708–721 (2021)
[29]
Korman, A., Kutten, S., Peleg, D.: Proof labeling schemes. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Principles of Distributed Computing, pp. 9–18 (2005)
[30]
Kalai, Y., Lombardi, A., Vaikuntanathan, V., Wichs, D.: Boosting batch arguments and RAM delegation. In: Proceedings of the 55th Annual ACM Symposium on Theory of Computing (STOC), pp. 1545–1552 (2023)
[31]
Kol, G., Oshman, R., Saxena, R.R.: Interactive distributed proofs. In: Symposium on Principles of Distributed Computing (PODC), pp. 255–264 (2018)
[32]
Kutten S and Peleg D Fast distributed construction of small k-dominating sets and applications J. Algor. 1998 28 27
[33]
Kalai Y and Paneth O Hirt M and Smith A Delegating RAM computations Theory of Cryptography 2016 Heidelberg Springer 91-118
[34]
Kalai, Y.T., Paneth, O., Yang, L.: How to delegate computations publicly. In: Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, pp. 1115–1124 (2019)
[35]
Kalai, Y.T., Raz, R., Rothblum, R.D.: Delegation for bounded space. In Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing, pp. 565–574 (2013)
[36]
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)
[37]
Lynch NA Distributed Algorithms 1996 Burlington Morgan Kaufmann
[38]
Merkle RC Brassard G A certified digital signature Advances in Cryptology — CRYPTO’ 89 Proceedings 1990 New York Springer 218-238
[39]
Micali S Computationally sound proofs SIAM J. Comput. 2000 30 4 1253-1298
[40]
Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. In: Chawla, S. (ed.) Symposium on Discrete Algorithms (SODA), pp. 1096–115 (2020)
[41]
Ostrovsky R, Perry M, and Rosenbaum W Das S and Tixeuil S Space-time tradeoffs for distributed verification Structural Information and Communication Complexity 2017 Cham Springer 53-70
[42]
Peleg D Distributed Computing: A Locality-Sensitive Approach 2000 Philadelphia Society for Industrial and Applied Mathematics
[43]
Patt-Shamir B and Perry M Spirakis P and Tsigas P Proof-labeling schemes: broadcast, unicast and in between Stabilization, Safety, and Security of Distributed Systems 2017 Cham Springer 1-17
[44]
Sarma, A.D., et al. Distributed verification and hardness of distributed approximation. SIAM J. Comput. (special issue of STOC 2011) (2012)
[45]
Waters B and Wu DJ Dodis Y and Shrimpton T Batch arguments for and more from standard bilinear group assumptions Advances in Cryptology – CRYPTO 2022 2022 Heidelberg Springer 433-463
Index Terms
- Locally Verifiable Distributed SNARGs
Index terms have been assigned to the content through auto-classification.
Recommendations
Publicly verifiable ciphertexts
Advances in Security for Communication NetworksIn many applications where encrypted traffic flows from an open public domain to a protected private domain there exists a gateway that bridges these two worlds, faithfully forwarding all incoming traffic to the receiver. We observe that the notion of ...
Locally Verifiable Signature and Key Aggregation
Advances in Cryptology – CRYPTO 2022AbstractAggregate signatures (Boneh, Gentry, Lynn, Shacham, Eurocrypt 2003) enable compressing a set of N signatures on N different messages into a short aggregate signature. This reduces the space complexity of storing the signatures from linear in N to ...
Batching Adaptively-Sound SNARGs for NP
Theory of CryptographyAbstractA succinct non-interactive argument (SNARG) for NP allows a prover to convince a verifier that an NP statement x is true with a proof whose size is sublinear in the length of the traditional NP witness. Moreover, a SNARG is adaptively sound if the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Nov 2023
511 pages
© International Association for Cryptologic Research 2023.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 29 November 2023
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 05 Mar 2025