Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
Automotive Acoustics Conference 2025

Call for Papers - Deadline: 01/13/2025. 

We would like to invite you to submit your proposals for a presentation and join us as we explore new practices in sustainable noise control. We are looking forward to your insights on innovative, eco-friendly, and smart ways to shape the future of automotive acoustics.
EXTENDED SEARCH
Log in
Top
Published in:
Read chapter Read first chapter

2025 | OriginalPaper | Chapter

Batch Arguments to NIZKs from One-Way Functions

Authors : Eli Bradley, Brent Waters, David J. Wu

Published in: Theory of Cryptography

Publisher: Springer Nature Switzerland

Log in

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

search-config
loading …

Abstract

Succinctness and zero-knowledge are two fundamental properties in the study of cryptographic proof systems. Several recent works have formalized the connections between these two notions by showing how to realize non-interactive zero-knowledge (NIZK) arguments from succinct non-interactive arguments. Specifically, Champion and Wu (CRYPTO 2023) as well as Bitansky, Kamath, Paneth, Rothblum, and Vasudevan (ePrint 2023) recently showed how to construct a NIZK argument for \(\textsf{NP}\) from a (somewhere-sound) non-interactive batch argument (BARG) and a dual-mode commitment scheme (and in the case of the Champion-Wu construction, a local pseudorandom generator). The main open question is whether a BARG suffices for a NIZK (just assuming one-way functions).
In this work, we first show that an adaptively-sound BARG for \(\textsf{NP}\) together with an one-way function imply a computational NIZK argument for \(\textsf{NP}\). We then show that the weaker notion of somewhere soundness achieved by existing BARGs from standard algebraic assumptions are also adaptively sound if we assume sub-exponential security. This transformation may also be of independent interest. Taken together, we obtain a NIZK argument for \(\textsf{NP}\) from one-way functions and a sub-exponentially-secure somewhere-sound BARG for \(\textsf{NP}\).
If we instead assume plain public-key encryption, we show that a standard polynomially-secure somewhere-sound batch argument for \(\textsf{NP}\) suffices for the same implication. As a corollary, this means a somewhere-sound BARG can be used to generically upgrade any semantically-secure public-key encryption scheme into one secure against chosen-ciphertext attacks. More broadly, our results demonstrate that constructing non-interactive batch arguments for \(\textsf{NP}\) is essentially no easier than constructing NIZK arguments for \(\textsf{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 Monotone Policy BARGs from BARGs and Additively Homomorphic Encryption
next chapter Security Bounds for Proof-Carrying Data from Straightline Extractors
Footnotes
1
A BARG satisfies somewhere soundness if the common reference string (CRS) can be programmed at a specific index i, and adaptive soundness is guaranteed with respect to the \({i}^{\mathrm {{th}}}\) statements \(x_i\). Moreover, the CRS (computationally) hides the special index i.
 
2
In an independent update that was concurrent to this work, the most recent revision of their work [4] also show how to construct computational NIZK arguments from batch arguments and one-way functions. We discuss the concurrent work at the end of this section.
 
3
The original version of their work (May 2023) [5] showed how to construct a statistical NIZK argument with a non-uniform prover from somewhere-sound BARGs and lossy public-key encryption. In a subsequent revision (June 2023) [3], they improved their result to obtain a statistical NIZK argument with a uniform prover from somewhere-sound BARGs and lossy public-key encryption. In the most recent revision (December 2023) [4], they additionally showed how to obtain a computational NIZK argument from somewhere-sound BARGs. These works also show additional implications between batch arguments and (statistical) witness indistinguishability.
 
4
Technically, the construction in [11] composes an arbitrary (sub-exponentially-secure) local PRG with a randomness extractor. Using the Gentry-Wichs leakage-simulation lemma [19] and assuming sub-exponential hardness of the local PRG, this yields a leakage-resilient local PRG. For ease of exposition, we describe their blueprint assuming a leakage-resilient local PRG.
 
5
As shown in [26, 34], this suffices for single-theorem zero-knowledge, which can be boosted to multi-theorem zero-knowledge using the classic transformation of [17].
 
Literature
1.
Bellare, M., Hofheinz, D., Yilek, S.: Possibility and impossibility results for encryption and commitment secure under selective opening. In: EUROCRYPT (2009)
2.
Bellare, M., Yung, M.: Certifying cryptographic tools: the case of trapdoor permutations. In: CRYPTO (1992)
3.
4.
5.
6.
Blum, M., Feldman, P. and Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: STOC (1988)
7.
8.
Brakerski, Z., Brodsky, M.F., Kalai, Y.T., Lombardi, A., Paneth, O.: SNARGs for monotone policy batch NP. In: CRYPTO (2023)
9.
Canetti, R., Halevi, S., Katz, J.: A forward-secure public-key encryption scheme. In: EUROCRYPT (2003)
10.
Canetti, R., Lichtenberg, A.: Certifying trapdoor permutations, revisited. In: TCC (2018)
11.
Champion, J., Wu, D.J.: Non-interactive zero-knowledge from non-interactive batch arguments. In: CRYPTO (2023)
12.
Choudhuri, A.R., Garg, S., Jain, A., Jin, Z., Zhang, J.: Correlation intractability and SNARGs from sub-exponential DDH. In: CRYPTO (2023)
13.
Choudhuri, A.R., Jain, A., Jin, Z.: Non-interactive batch arguments for NP from standard assumptions. In: CRYPTO (2021)
14.
Choudhuri, A.R., Jain, A., Jin, Z.: SNARGs for P from LWE. In: FOCS (2021)
15.
Damgård, I., Nielsen, J.B.: Perfect hiding and perfect binding universally composable commitment schemes with constant expansion factor. In: CRYPTO (2002)
16.
Devadas, L., Goyal, R., Kalai, Y., Vaikuntanathan, V.: Rate-1 non-interactive arguments for batch-NP and applications. In: FOCS (2022)
17.
Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string (extended abstract). In: FOCS (1990)
18.
Garg, R., Sheridan, K., Waters, B., Wu, D.J.: Fully succinct batch arguments for NP from indistinguishability obfuscation. In: TCC (2022)
19.
Gentry, C., Wichs, D.: Separating succinct non-interactive arguments from all falsifiable assumptions. In: STOC (2011)
20.
21.
Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof-systems (extended abstract). In: STOC (1985)
22.
Wee, H.C.L.A.A., Nguyen, H.W.D.J.T.: Leakage-resilient cryptography from minimal assumptions. In: EUROCRYPT (2013)
23.
Hulett, J., Jawale, R., Khurana, D., Srinivasan, A.: SNARGs for P from sub-exponential DDH and QR. In: EUROCRYPT (2022)
24.
Kalai, Y., Lombardi, A., Vaikuntanathan, V., Wichs, D.: Boosting batch arguments and RAM delegation. In: STOC (2023)
25.
Kalai, Y.T., Vaikuntanathan, V., Zhang, R.Y.: Somewhere statistical soundness, post-quantum security, and SNARGs. In: TCC (2021)
26.
Kitagawa, F., Matsuda, T., Yamakawa, T.: NIZK from SNARG. In: TCC (2020)
27.
Koppula, V., Waters, B.: Realizing chosen ciphertext security generically in attribute-based encryption and predicate encryption. In: CRYPTO (2019)
28.
Libert, B., Passelègue, A., Wee, H., Wu, D.J., New constructions of statistical NIZKs: Dual-mode DV-NIZKs and more. In: EUROCRYPT (2020)
29.
Lombardi, A., Quach, W., Rothblum, R.D., Wichs, D., Wu, D.J.: New constructions of reusable designated-verifier NIZKs. In: CRYPTO (2019)
30.
Matsuda, T.: Chosen ciphertext security via BARGs. IACR Cryptol. ePrint Arch. (2023)
31.
Naor, M.: Bit commitment using pseudo-randomness. In: CRYPTO (1989)
32.
Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: STOC (1990)
33.
Nassar, S., Waters, B., Wu, D.J.: Monotone policy BARGs from BARGs and additively homomorphic encryption. In: TCC (2024)
34.
Quach, W., Rothblum, R.D., Wichs, D.: Reusable designated-verifier NIZKs for all NP from CDH. In: EUROCRYPT (2019)
35.
Quach, W., Waters, B., Wichs, D.: Targeted lossy functions and applications. In: CRYPTO (2021)
36.
De Santis, A., Di Crescenzo, G., Ostrovsky, R., Persiano, G., Sahai, A.: Robust non-interactive zero knowledge. In: CRYPTO, Rafail Ostrovsky (2001)
37.
Waters, B.: A new approach for non-interactive zero-knowledge from learning with errors. In: STOC, pp. 399–410 (2024)
38.
39.
Waters, B., Wu, D.J.: Batch arguments for NP and more from standard bilinear group assumptions. In: CRYPTO (2022)
40.
Waters, B., Wu, D.J.: Adaptively-sound succinct arguments for NP from indistinguishability obfuscation. In: STOC, pp. 387–398 (2024)
41.
Waters, B., Wu, D.J.: A pure indistinguishability obfuscation approach to adaptively-sound SNARGs for NP. IACR Cryptol. ePrint Arch., p. 933 (2024)
42.
Waters, B., Zhandry, M.: Adaptive security in SNARGs via iO and lossy functions. In: CRYPTO, pp. 72–104 (2024)
Metadata
Title
Batch Arguments to NIZKs from One-Way Functions
Authors
Eli Bradley
Brent Waters
David J. Wu
Copyright Year
2025
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_15

Premium Partner

    Image Credits