Batch Arguments for  $$\textsf{NP}$$ and More from Standard Bilinear Group Assumptions | SpringerLink
Skip to main content
Springer Nature Link
Log in

Batch Arguments for \(\textsf{NP}\) and More from Standard Bilinear Group Assumptions

  • Conference paper
  • First Online:
Advances in Cryptology – CRYPTO 2022 (CRYPTO 2022)

Part of the book series: Lecture Notes in Computer Science ((LNCS,volume 13508))

Included in the following conference series:

  • 1621 Accesses

Abstract

Non-interactive batch arguments for \(\textsf{NP}\) provide a way to amortize the cost of \(\textsf{NP}\) verification across multiple instances. They enable a prover to convince a verifier of multiple \(\textsf{NP}\) statements with communication much smaller than the total witness length and verification time much smaller than individually checking each instance.

   In this work, we give the first construction of a non-interactive batch argument for \(\textsf{NP}\) from standard assumptions on groups with bilinear maps (specifically, from either the subgroup decision assumption in composite-order groups or from the \(k\)-\(\textsf{Lin}\) assumption in prime-order groups for any \(k \ge 1\)). Previously, batch arguments for \(\textsf{NP}\) were only known from \(\textsf{LWE}\), or a combination of multiple assumptions, or from non-standard/non-falsifiable assumptions. Moreover, our work introduces a new direct approach for batch verification and avoids heavy tools like correlation-intractable hash functions or probabilistically-checkable proofs common to previous approaches.

   As corollaries to our main construction, we obtain the first publicly-verifiable non-interactive delegation scheme for RAM programs (i.e., a succinct non-interactive argument (SNARG) for \(\textsf{P}\)) with a CRS of sublinear size (in the running time of the RAM program), as well as the first aggregate signature scheme (supporting bounded aggregation) from standard assumptions on bilinear maps.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 5719
Price includes VAT (Japan)
  • Available as EPUB and PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 7149
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Similar content being viewed by others

Notes

  1. 1.

    In the bilateral version of the \(k\)-\(\textsf{Lin}\) assumption, the challenge is encoded in both groups rather than one of the groups.

  2. 2.

    Recall that the case \(k = 1\) corresponds to the \(\textsf{DDH}\) assumption holding in each base group (i.e., \(\textsf{SXDH}\)). The case \(k = 2\) corresponds to the \(\textsf{DLIN}\) assumption [BBS04, HK07, Sha07].

  3. 3.

    Technically, this is only required for the input wires corresponding to the witness.

  4. 4.

    Our techniques extend naturally to support binary-valued gates that can compute arbitrary quadratic functions of their inputs; see the full version of this paper [WW22].

  5. 5.

    This is different from the notion of “dual-mode” proof system often encountered in the setting of non-interactive zero-knowledge (NIZK) [GOS06, PS19, LPWW20]. There, the CRS can be sampled in two computationally indistinguishable modes: one mode ensures statistical soundness and the other ensures statistical zero knowledge.

  6. 6.

    Our construction satisfies the stronger notion of semi-adaptive somewhere soundness [CJJ21b], where the adversary first commits to an index \(i^*\), but is allowed to choose the statements \((\textbf{x}_1, \ldots , \textbf{x}_m)\) after seeing the CRS. The adversary wins if the proof is valid but \(\textbf{x}_{i^*}\) is false. This notion is needed for the implications to delegation.

  7. 7.

    While our BARG scheme can be based on the \(k\)-\(\textsf{Lin}\) assumption over bilinear groups for any \(k \ge 1\), existing constructions of somewhere statistically binding hash functions [OPWW15] rely on the \(\textsf{DDH}\) assumption. As such, our current instantiation is based on \(\textsf{SXDH}\). It seems plausible that the \(\textsf{DDH}\)-based construction of somewhere statistically binding hash functions can be extended to achieve hardness under the \(k\)-\(\textsf{Lin}\) assumption, but this is orthogonal to the primary focus of our work.

  8. 8.

    Here, we allow the verification algorithm to take in a separate verification key \(\textsf{vk}\), which may be shorter than the full common reference string \(\textsf{crs}\). Note that the \(\textsf{vk}\) is assumed to be public (i.e., the CRS contains \(\textsf{vk}\) and possibly additional components used to construct proofs).

References

  1. Ahn, J.H., Green, M., Hohenberger, S.: Synchronized aggregate signatures: new definitions, constructions and applications. In: ACM CCS (2010)

    Google Scholar 

  2. Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. IACR Cryptol. ePrint Arch. 2018, 1–83 (2018)

    Google Scholar 

  3. Boneh, D., Boyen, X., Shacham, H.: Short group signatures. In: Franklin, M. (ed.) CRYPTO 2004. LNCS, vol. 3152, pp. 41–55. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-28628-8_3

    Chapter  Google Scholar 

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

    Article  MathSciNet  Google Scholar 

  5. Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: ITCS (2012)

    Google Scholar 

  6. Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., Ostrovsky, R.: Succinct non-interactive arguments via linear interactive proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 315–333. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36594-2_18

    Chapter  Google Scholar 

  7. Bitansky, N., Canetti, R., Paneth, O., Rosen, A.: On the existence of extractable one-way functions. In: STOC (2014)

    Google Scholar 

  8. Boneh, D., Gentry, C., Lynn, B., Shacham, H.: Aggregate and verifiably encrypted signatures from bilinear maps. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 416–432. Springer, Heidelberg (2003). https://doi.org/10.1007/3-540-39200-9_26

    Chapter  Google Scholar 

  9. Boneh, D., Goh, E.-J., Nissim, K.: Evaluating 2-DNF formulas on ciphertexts. In: Kilian, J. (ed.) TCC 2005. LNCS, vol. 3378, pp. 325–341. Springer, Heidelberg (2005). https://doi.org/10.1007/978-3-540-30576-7_18

    Chapter  Google Scholar 

  10. Brakerski, Z., Holmgren, J., Kalai, Y.T.: Non-interactive delegation and batch NP verification from standard computational assumptions. In: STOC (2017)

    Google Scholar 

  11. 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. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 247–277. Springer, Cham (2017). https://doi.org/10.1007/978-3-319-56617-7_9

    Chapter  Google Scholar 

  12. Canetti, R., et al.: Fiat-Shamir: from practice to theory. In: STOC (2019)

    Google Scholar 

  13. Catalano, D., Fiore, D.: Vector commitments and their applications. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 55–72. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-36362-7_5

    Chapter  Google Scholar 

  14. Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited (preliminary version). In: STOC (1998)

    Google Scholar 

  15. Chiesa, A., Hu, Y., Maller, M., Mishra, P., Vesely, N., Ward, N.: Marlin: preprocessing zkSNARKs with universal and updatable SRS. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 738–768. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_26

    Chapter  Google Scholar 

  16. 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_14

    Chapter  Google Scholar 

  17. Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for P from LWE. In: FOCS (2021)

    Google Scholar 

  18. Chiesa, A., Ojha, D., Spooner, N.: Fractal: post-quantum and transparent recursive proofs from holography. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12105, pp. 769–793. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45721-1_27

    Chapter  Google Scholar 

  19. 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). https://doi.org/10.1007/978-3-642-28914-9_4

    Chapter  Google Scholar 

  20. Freire, E.S.V., Hofheinz, D., Paterson, K.G., Striecks, C.: Programmable hash functions in the multilinear setting. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8042, pp. 513–530. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-40041-4_28

    Chapter  MATH  Google Scholar 

  21. Freeman, D.M.: Converting pairing-based cryptosystems from composite-order groups to prime-order groups. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 44–61. Springer, Heidelberg (2010). https://doi.org/10.1007/978-3-642-13190-5_3

    Chapter  Google Scholar 

  22. Fiat, A., Shamir, A.: How to prove yourself: practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO 1986. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (1987). https://doi.org/10.1007/3-540-47721-7_12

    Chapter  Google Scholar 

  23. 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). https://doi.org/10.1007/978-3-642-38348-9_37

    Chapter  Google Scholar 

  24. Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: STOC (2008)

    Google Scholar 

  25. Groth, J., Ostrovsky, R., Sahai, A.: Perfect non-interactive zero knowledge for NP. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 339–358. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_21

    Chapter  Google Scholar 

  26. Gentry, C., Ramzan, Z.: Identity-based aggregate signatures. In: Yung, M., Dodis, Y., Kiayias, A., Malkin, T. (eds.) PKC 2006. LNCS, vol. 3958, pp. 257–273. Springer, Heidelberg (2006). https://doi.org/10.1007/11745853_17

    Chapter  Google Scholar 

  27. 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). https://doi.org/10.1007/978-3-642-17373-8_19

    Chapter  Google Scholar 

  28. Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305–326. Springer, Heidelberg (2016). https://doi.org/10.1007/978-3-662-49896-5_11

    Chapter  Google Scholar 

  29. Groth, J., Sahai, A.: Efficient non-interactive proof systems for bilinear groups. In: Smart, N. (ed.) EUROCRYPT 2008. LNCS, vol. 4965, pp. 415–432. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78967-3_24

    Chapter  Google Scholar 

  30. Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: STOC (2011)

    Google Scholar 

  31. González, A., Zacharakis, A.: Succinct publicly verifiable computation. In: TCC (2021)

    Google Scholar 

  32. 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. EUROCRYPT 2022. Lecture Notes in Computer Science, vol. 13276, pp. 520–549. Springer, Cham (2022). https://doi.org/10.1007/978-3-031-07085-3_18

  33. Hofheinz, D., Kiltz, E.: Secure hybrid encryption from weakened key encapsulation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 553–571. Springer, Heidelberg (2007). https://doi.org/10.1007/978-3-540-74143-5_31

    Chapter  Google Scholar 

  34. Hohenberger, S., Koppula, V., Waters, B.: Universal signature aggregators. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 3–34. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-46803-6_1

    Chapter  Google Scholar 

  35. Hubácek, P., Wichs, D.: On the communication complexity of secure function evaluation with long output. In: ITCS (2015)

    Google Scholar 

  36. Hohenberger, S., Waters, B.: Synchronized aggregate signatures from the RSA assumption. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10821, pp. 197–229. Springer, Cham (2018). https://doi.org/10.1007/978-3-319-78375-8_7

    Chapter  Google Scholar 

  37. Jain, A., Jin, Z.: Non-interactive Zero Knowledge from Sub-exponential DDH. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12696, pp. 3–32. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77870-5_1

    Chapter  Google Scholar 

  38. Jawale, R., Kalai, Y.T, Khurana, D., Zhang, R.Y.: SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE. In: STOC (2021)

    Google Scholar 

  39. Kalai, Y.T., Paneth, O., Yang, L.: How to delegate computations publicly. In: STOC (2019)

    Google Scholar 

  40. Kalai, Y.T., Raz, R., Rothblum, R.D.: Delegation for bounded space. In: STOC (2013)

    Google Scholar 

  41. Kalai, Y.T., Raz, R., Rothblum, R.D.: How to delegate computations: the power of no-signaling proofs. In: STOC (2014)

    Google Scholar 

  42. 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, vol. 13042, pp. 330–368. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-90459-3_12

    Chapter  Google Scholar 

  43. Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. In: FOCS (1990)

    Google Scholar 

  44. 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, vol. 8269, pp. 41–60. Springer, Heidelberg (2013). https://doi.org/10.1007/978-3-642-42033-7_3

    Chapter  Google Scholar 

  45. Lysyanskaya, A., Micali, S., Reyzin, L., Shacham, H.: Sequential aggregate signatures from trapdoor permutations. In: Cachin, C., Camenisch, J.L. (eds.) EUROCRYPT 2004. LNCS, vol. 3027, pp. 74–90. Springer, Heidelberg (2004). https://doi.org/10.1007/978-3-540-24676-3_5

    Chapter  Google Scholar 

  46. Lu, S., Ostrovsky, R., Sahai, A., Shacham, H., Waters, B.: Sequential aggregate signatures and multisignatures without random oracles. In: Vaudenay, S. (ed.) EUROCRYPT 2006. LNCS, vol. 4004, pp. 465–485. Springer, Heidelberg (2006). https://doi.org/10.1007/11761679_28

    Chapter  Google Scholar 

  47. Lipmaa, H., Pavlyk, K.: Gentry-wichs is tight: a falsifiable non-adaptively sound SNARG. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021. LNCS, vol. 13092, pp. 34–64. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-92078-4_2

    Chapter  Google Scholar 

  48. Libert, B., Passelègue, A., Wee, H., Wu, D.J.: New constructions of statistical NIZKs: Dual-Mode DV-NIZKs and more. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 410–441. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-45727-3_14

    Chapter  Google Scholar 

  49. Micali, S.: Computationally-sound proofs. In: Proceedings of the Annual European Summer Meeting of the Association of Symbolic Logic (1995)

    Google Scholar 

  50. Naor, M.: On cryptographic assumptions and challenges. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 96–109. Springer, Heidelberg (2003). https://doi.org/10.1007/978-3-540-45146-4_6

    Chapter  Google Scholar 

  51. Okamoto, T., Pietrzak, K., Waters, B., Wichs, D.: New realizations of somewhere statistically binding hashing and positional accumulators. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 121–145. Springer, Heidelberg (2015). https://doi.org/10.1007/978-3-662-48797-6_6

    Chapter  Google Scholar 

  52. Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: IEEE Symposium on Security and Privacy (2013)

    Google Scholar 

  53. Peikert, C., Shiehian, S.: Noninteractive zero knowledge for NP from (plain) learning with errors. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 89–114. Springer, Cham (2019). https://doi.org/10.1007/978-3-030-26948-7_4

    Chapter  Google Scholar 

  54. Rothblum, G.N., Rothblum, R.D.: Batch verification and proofs of proximity with polylog overhead. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 108–138. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64378-2_5

    Chapter  MATH  Google Scholar 

  55. Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. In: STOC (2016)

    Google Scholar 

  56. Reingold, O., Rothblum, G.N., Rothblum, R.D.: Efficient batch verification for UP. In: CCC (2018)

    Google Scholar 

  57. Rückert, M., Schröder, D.: Aggregate and verifiably encrypted signatures from multilinear maps without random oracles. In: Park, J.H., Chen, H.-H., Atiquzzaman, M., Lee, C., Kim, T., Yeo, S.-S. (eds.) ISA 2009. LNCS, vol. 5576, pp. 750–759. Springer, Heidelberg (2009). https://doi.org/10.1007/978-3-642-02617-1_76

    Chapter  Google Scholar 

  58. Setty, S.: Spartan: efficient and general-purpose zkSNARKs without trusted setup. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 704–737. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-56877-1_25

    Chapter  Google Scholar 

  59. Shamir, A.: IP=PSPACE. In: FOCS (1990)

    Google Scholar 

  60. Shacham, H.: A Cramer-Shoup encryption scheme from the linear assumption and from progressively weaker linear variants. IACR Cryptol. ePrint Arch. (2007)

    Google Scholar 

  61. Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: STOC (2014)

    Google Scholar 

  62. Wichs, D.: Personal communication (2022)

    Google Scholar 

  63. Waters, B., Wu, D.J.: Batch arguments for NP and more from standard bilinear group assumptions. IACR Cryptol. ePrint Arch. (2022)

    Google Scholar 

Download references

Acknowledgments

B. Waters is supported by NSF CNS-1908611, a Simons Investigator award, and the Packard Foundation Fellowship. D. J. Wu is supported by NSF CNS-1917414, CNS-2045180, a Microsoft Research Faculty Fellowship, and a Google Research Scholar award.

Author information

Authors and Affiliations

  1. University of Texas at Austin, Austin, TX, USA

    Brent Waters & David J. Wu

  2. NTT Research, Sunnyvale, CA, USA

    Brent Waters

Authors
  1. Brent Waters
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. David J. Wu
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to David J. Wu .

Editor information

Editors and Affiliations

  1. New York University, New York, NY, USA

    Yevgeniy Dodis

  2. University of Florida, Gainesville, FL, USA

    Thomas Shrimpton

Rights and permissions

Reprints and permissions

Copyright information

© 2022 International Association for Cryptologic Research

About this paper

Check for updates. Verify currency and authenticity via CrossMark

Cite this paper

Waters, B., Wu, D.J. (2022). Batch Arguments for \(\textsf{NP}\) and More from Standard Bilinear Group Assumptions. In: Dodis, Y., Shrimpton, T. (eds) Advances in Cryptology – CRYPTO 2022. CRYPTO 2022. Lecture Notes in Computer Science, vol 13508. Springer, Cham. https://doi.org/10.1007/978-3-031-15979-4_15

Download citation

  • DOI: https://doi.org/10.1007/978-3-031-15979-4_15

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-031-15978-7

  • Online ISBN: 978-3-031-15979-4

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics

Societies and partnerships