Top

Published in:

2025 | OriginalPaper | Chapter

Batching Adaptively-Sound SNARGs for NP

Authors : Lalita Devadas, Brent Waters, David J. Wu

Published in: Theory of Cryptography

Publisher: Springer Nature Switzerland

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

A 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 adversary can choose the statement it wants to prove after seeing the scheme parameters. Very recently, Waters and Wu (STOC 2024) showed how to construct adaptively-sound SNARGs for NP in the plain model from falsifiable assumptions (specifically, sub-exponentially secure indistinguishability obfuscation, sub-exponentially secure one-way functions, and polynomial hardness of discrete log).

We consider the batch setting where the prover wants to prove a collection of T statements \(x_1, \ldots , x_T\) and its goal is to construct a proof whose size is sublinear in both the size of a single witness and the number of instances T. In this setting, existing constructions either require the size of the public parameters to scale linearly with T (and thus, can only support an a priori bounded number of instances), or only provide non-adaptive soundness, or have proof size that scales linearly with the size of a single NP witness. In this work, we give two approaches for batching adaptively-sound SNARGs for NP, and in particular, show that under the same set of assumptions as those underlying the Waters-Wu adaptively-sound SNARG, we can obtain an adaptively-sound SNARG for batch NP where the size of the proof is \(\textsf{poly} (\lambda )\) and the size of the CRS is \(\textsf{poly} (\lambda + |C|)\), where \(\lambda \) is a security parameter and |C| is the size of the circuit that computes the associated NP relation.

Our first approach builds directly on top of the Waters-Wu construction and relies on indistinguishability obfuscation and a homomorphic re-randomizable one-way function. Our second approach shows how to combine ideas from the Waters-Wu SNARG with the chaining-based approach by Garg, Sheridan, Waters, and Wu (TCC 2022) to obtain a SNARG for batch NP.

Dont have a licence yet? Then find out more about our products and how to get one now:

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!

inform now

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!

inform now

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!

inform now

previous chapter Worst-Case to Average-Case Hardness of LWE: An Alternative Perspective

next chapter Doubly-Efficient Batch Verification in Statistical Zero-Knowledge

A subsequent work [41] also shows how to construct an adaptively-sound SNARG using \(i\mathcal {O} \) and sub-exponentially-secure one-way functions without any additional algebraic assumptions.

A BARG is somewhere extractable if the CRS can be programmed on a (hidden) index \(i \in [T]\). Then, given a valid BARG proof \(\pi \) on a batch of statements \((x_1, \ldots , x_T)\), there is an efficient extraction algorithm that recovers a witness \(w_i\) for \(x_i\). The special index i is computationally hidden by the CRS. Somewhere extractable BARGs can be constructed from most number-theoretic assumptions [12‐14, 17, 23, 26, 27, 29, 36, 39].

Note that the original Waters-Wu construction did not require \(\textsf{GenSol}\) and \(\textsf{GenChall}\) to take the bit \(b \in \{0, 1\}\) as input. Instead, \(\textsf{GenSol}\) computed \(b = \textsf{F} (k_{\textsf{sel} }, x)\) and outputted \(z = \textsf{F} (k_b, x)\) while \(\textsf{GenChall}\) simply outputted \(f(\textsf{F} (k_0, x))\) and \(f(\textsf{F} (k_1, x))\). The adaptation here is equivalent to the original Waters-Wu construction and the updated syntax will be conducive when extending to batch arguments.

This is the notion of succinctness that our constructions achieve.

Albrecht, M.R., Cini, V., Lai, R.W.F., Malavolta, G., Thyagarajan, S.A.K.: Lattice-based SNARKs: publicly verifiable, preprocessing, and recursively composable: (extended abstract). In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, vol. 13508, Part II, pp. 102–132. Springer, Cham (2022)

Barak, B., et al.: On the (im)possibility of obfuscating programs. In: Kilian, J. (ed.) CRYPTO 2001. LNCS, vol. 2139, pp. 1–18. Springer, Heidelberg (2001)

Bitansky, N., et al.: The hunting of the SNARK. J. Cryptol. 30(4), 989–1066 (2017)

Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Goldwasser, S. (ed.) ITCS 2012, pp. 326–349. ACM (2012)

Bitansky, N., Canetti, R., Paneth, O., Rosen, A.: On the existence of extractable one-way functions. In: Shmoys, D.B. (ed.) 46th ACM STOC, pp. 505–514. ACM Press (2014)

Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., Paneth, O.: Succinct non-interactive arguments via linear interactive proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 315–333. Springer, Heidelberg (2013)

Boneh, D., Ishai, Y., Sahai, A., Wu, D.J.: Lattice-based SNARGs and their application to more efficient obfuscation. In: Coron, J.-S., Nielsen, J.B. (ed.) EUROCRYPT 2017, Part III, LNCS, vol. 10212, pp. 247–277. Springer, Heidelberg (2017)

Boneh, D., Waters, B.: Constrained pseudorandom functions and their applications. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013, LNCS, Part II, vol. 8270, pp. 280–300. Springer, Heidelberg (2013)

Boyle, E., Goldwasser, S., Ivan, I.: Functional signatures and pseudorandom functions. In: Krawczyk, H. (ed.) PKC 2014. LNCS, vol. 8383, pp. 501–519. Springer, Heidelberg (2014)

10.

Brakerski, Z., Brodsky, M.F., Kalai, Y.T., Lombardi, A., Paneth, O.: SNARGs for monotone policy batch NP. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, Part II, vol. 14082, pp. 252–283. Springer, Heidelberg (2023)

11.

Chiesa, A., Tromer, E.: Proof-carrying data and hearsay arguments from signature cards. In: Yao, A.C.-C. (ed.) ICS 2010, pp. 310–331. Tsinghua University Press (2010)

12.

Choudhuri, A.R., Garg, S., Jain, A., Jin, Z., Zhang, J.: Correlation intractability and SNARGs from sub-exponential DDH. In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, Part IV, vol. 14084, pp. 635–668. Springer, Heidelberg (2023)

13.

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, Part IV, vol. 12828, pp. 394–423. Springer, Heidelberg (2021), Virtual Event

14.

Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for \(\cal{P}\) from LWE. In: 62nd FOCS, pp. 68–79. IEEE Computer Society Press (2022)

15.

Cini, V., Lai, R.W.F., Malavolta, G.: Lattice-based succinct arguments from vanishing polynomials - (extended abstract). In: Handschuh, H., Lysyanskaya, A. (eds.) CRYPTO 2023. LNCS, Part II, vol. 14082, pp. 72–105. Springer, Heidelberg (2023)

16.

Damgård, I., Faust, S., Hazay, C.: Secure two-party computation with low communication. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 54–74. Springer, Heidelberg (2012)

17.

Devadas, L., Goyal, R., Kalai, Y., Vaikuntanathan, V.: Rate-1 non-interactive arguments for batch-NP and applications. In: 63rd FOCS, pp. 1057–1068. IEEE Computer Society Press (2022)

18.

Garg, R., Sheridan, K., Waters, B., David, J.W.: Fully succinct batch arguments for NP from indistinguishability obfuscation. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022. LNCS, Part I, vol. 13747, pp. 526–555. Springer, Heidelberg (2022)

19.

Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626–645. Springer, Heidelberg (2013)CrossRef

20.

Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC, pp. 99–108. ACM Press (2011)

21.

Groth, J.: Short pairing-based non-interactive zero-knowledge arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321–340. Springer, Heidelberg (2010)CrossRef

22.

Hubacek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: Roughgarden, T. (ed.) ITCS 2015, pp. 163–172. ACM (2015)

23.

Hulett, J., Jawale, R., Khurana, D., Srinivasan, A.: SNARGs for P from sub-exponential DDH and QR. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, Part II, vol. 13276, pp. 520–549. Springer, Heidelberg (2022)

24.

Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from well-founded assumptions. In: Khuller, S., Williams, V.V. (eds.) 53rd ACM STOC, pp. 60–73. ACM Press (2021)

25.

Jain, A., Lin, H., Sahai, A.: Indistinguishability obfuscation from LPN over \(\mathbb{F}_{p}\), DLIN, and PRGs in \({NC}^0\). In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022. LNCS, Part I, vol. 13275, pages 670–699. Springer, Heidelberg (2022)

26.

Kalai, Y., Lombardi, A., Vaikuntanathan, V., Wichs, D.: Boosting batch arguments and RAM delegation. In: Saha, B., Servedio, R.A., (eds.) 55th ACM STOC, pp. 1545–1552. ACM Press (2023)

27.

Kalai, Y.T., Lombardi, A., Vaikuntanathan, V.: SNARGs and PPAD hardness from the decisional Diffie-Hellman assumption. In: Hazay, C., Stam, M. (eds.) EUROCRYPT 2023. LNCS, Part II, vol. 14005, pp. 470–498. Springer, Heidelberg (2023)

28.

Kalai, Y.T., Paneth, O., Yang, L.: How to delegate computations publicly. In: Charikar, M., Cohen, E. (eds.) 51st ACM STOC, pp. 1115–1124. ACM Press (2019)

29.

Kalai, Y.T., Vaikuntanathan, V., Zhang, R.Y.: Somewhere statistical soundness, post-quantum security, and SNARGs. In: Nissim, K., Waters, B. (eds.) TCC 2021. LNCS, Part I, vol. 13042, pp. 330–368. Springer, Heidelberg (2021)

30.

Kiayias, A., Papadopoulos, S., Triandopoulos, N., Zacharias, T.: Delegatable pseudorandom functions and applications. In: Sadeghi, A.-R., Gligor, V.D., Yung, M. (eds.) ACM CCS 2013, pp. 669–684. ACM Press (2013)

31.

Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: 4th ACM STOC, pp. 723–732. ACM Press (1992)

32.

Lipmaa, H.: Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes. In: Sako, K., Sarkar, P. (eds.) ASIACRYPT 2013. LNCS, Part I, vol. 8269, pp. 41–60. Springer, Heidelberg (2013)

33.

Mathialagan, S., Peters, S., Vaikuntanathan, V.: Adaptively sound zero-knowledge SNARKs for UP. In: CRYPTO (2024)

34.

Micali, S.: CS proofs (extended abstracts). In: 35th FOCS, pp. 436–453. IEEE Computer Society Press (1994)

35.

Nassar, S., Waters, B., Wu, D.J.: Monotone policy BARGs from BARGs and additively homomorphic encryption. In: TCC (2024)

36.

Paneth, O., Pass, R.: Incrementally verifiable computation via rate-1 batch arguments. In: 63rd FOCS, pp. 1045–1056. IEEE Computer Society Press (2022)

37.

Sahai, A., Waters, B:. How to use indistinguishability obfuscation: deniable encryption, and more. In: Shmoys, D.B. (ed.) 46th ACM STOC, pp. 475–484. ACM Press (2014)

38.

Valiant, P.: Incrementally verifiable computation or proofs of knowledge imply time/space efficiency. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 1–18. Springer, Heidelberg (2008)

39.

Waters, B., David, J.W.: Batch arguments for NP and more from standard bilinear group assumptions. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022. LNCS, Part II, vol. 13508, pp. 433–463. Springer, Heidelberg (2022)

40.

Waters, B., Wu, D.J.: Adaptively-sound succinct arguments for NP from indistinguishability obfuscation. In: STOC (2024)

41.

Waters, B., Wu, D.J.: A pure indistinguishability obfuscation approach to adaptively-sound SNARGs for NP. Cryptology ePrint Archive, Paper 2024/933 (2024)

42.

Waters, B., Zhandry, M.: Adaptive security in SNARGs via iO and lossy functions. In: CRYPTO (2024)

Title: Batching Adaptively-Sound SNARGs for NP
Authors: Lalita Devadas
Brent Waters
David J. Wu
Publisher: Springer Nature Switzerland
Book: Theory of Cryptography
Print ISBN: 978-3-031-78016-5

Electronic ISBN: 978-3-031-78017-2

Copyright Year: 2025
DOI: https://doi.org/10.1007/978-3-031-78017-2_12

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"