Top

Published in:

2025 | OriginalPaper | Chapter

Doubly-Efficient Batch Verification in Statistical Zero-Knowledge

Authors : Or Keret, Ron D. Rothblum, Prashant Nalini Vasudevan

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 sequence of recent works, concluding with Mu et al. (Eurocrypt, 2024) has shown that every problem \(\varPi \) admitting a non-interactive statistical zero-knowledge proof (\(\text {NISZK}\)) has an efficient zero-knowledge batch verification protocol. Namely, an \(\text {NISZK}\) protocol for proving that \(x_1,\dots ,x_k \in \varPi \) with communication that only scales poly-logarithmically with k. A caveat of this line of work is that the prover runs in exponential-time, whereas for \(\text {NP}\) problems it is natural to hope to obtain a doubly-efficient proof – that is, a prover that runs in polynomial-time given the k \(\text {NP}\) witnesses.

In this work we show that every problem in \(\text {NISZK}\cap \text {UP}\) has a doubly-efficient interactive statistical zero-knowledge proof with communication \(\textrm{poly}(n,\log (k))\) and \(\textrm{poly}(\log (k),\log (n))\) rounds. The prover runs in time \(\textrm{poly}(n,k)\) given access to the k \(\text {UP}\) witnesses. Here n denotes the length of each individual input, and \(\text {UP}\) is the subclass of \(\text {NP}\) relations in which YES instances have unique witnesses.

This result yields doubly-efficient statistical zero-knowledge batch verification protocols for a variety of concrete and central cryptographic problems from the literature.

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 Batching Adaptively-Sound SNARGs for NP

next chapter Monotone Policy BARGs from BARGs and Additively Homomorphic Encryption

Available only for authorised users

Doubly-efficient proofs are also studied in the context of problems in \(\text {P}\) (rather than \(\text {NP}\)) in which case we require the prover to run in polynomial-time, without any additional auxiliary information. See the recent survey by Goldreich [Gol18].

For batch verification of QR, there is a simple reduction from k instances to 1 by taking a random modular subset product of the given integers. However, this only works in case we use the same modulus for each instance whereas our protocol works even when using different moduli. Also, we note that [BDSMP91] only give an \(\text {NISZK}\) for QNR. However, in case N is a Blum integer, QR reduces to QNR by multiplying the input by \(-1 \pmod N\) (since \(-1\) is a QNR modulo a Blum integer).

Here we need a combiner between k commitments, which needs to be hiding if all of them are hiding, and binding if at least one of them is binding. A suitable combiner in this setting is to simply commit separately using each commitment scheme.

The later work of Ong and Vadhan [OV08] constructs instance-dependent commitments for all of \(\text {SZK}\). However, their construction is more complex and the simpler construction of instance-dependent commitments for \(\text {NISZK}\), due to [NV06], suffices for our results.

The commitment scheme, as presented in [NV06], was for a different promise problem known as \(\text {EA}\). However, it involved a preprocessing step intended to transform an \(\text {EA}\) instance into an Image Density instance. Since we will work directly with Image Density instances, we skip this preprocessing step.

We slightly abuse notation here since \(C_{V_{\text {UP}}}\) does not compute the functionality f (Note that f has \(\ell +1\) inputs while \(C_{V_{\text {UP}}}\) only has two). This abuse of notation is justified since the sizes of \(C_{V_{\text {UP}}}\) and the closely related circuit that computes f differ only by a multiplicative factor of \(\textrm{poly}(\ell )\), and \(\ell \) is constant.

Recall that the collision probability of a distribution X is defined as \(\text {cp}(X) = \mathop {\textrm{Pr}}\limits _{x,x'\leftarrow X} \left[ x=x' \right] \).

To facilitate the recursion, we need to rely on a protocol that does batch verification and additionally checks some (small-depth) predicate on the k witnesses.

[AL17]

Asharov, G., Lindell, Y.: A full proof of the BGW protocol for perfectly secure multiparty computation. J. Cryptol. 30(1), 58–151 (2017)MathSciNetCrossRef

[BDSMP91]

Blum, M., De Santis, A., Micali, S., Persiano, G.: Noninteractive zero-knowledge. SIAM J. Comput. 20(6), 1084–1118 (1991)MathSciNetCrossRef

[BGW88]

Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation (extended abstract). In: Simon, J. (eds.) Proceedings of the 20th Annual ACM Symposium on Theory of Computing, May 2–4, 1988, Chicago, Illinois, USA, pp. 1–10. ACM (1988)

[BKP+23]

Bitansky, N., Kamath, C., Paneth, O., Rothblum, R., Vasudevan, P.N.: Batch proofs are statistically hiding. Electron. Colloquium Comput. Complex., TR23-077 (2023)

[BMO90]

Bellare, M., Micali, S., Ostrovsky, R.M.: Perfect zero-knowledge in constant rounds. In: Symposium on the Theory of Computing (1990)

[BOGG+90]

Ben-Or, M., et al.: Everything provable is provable in zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 37–56. Springer, New York (1990). https://doi.org/10.1007/0-387-34799-2_4CrossRef

[DHRS07]

Ding, Y.Z., Harnik, D., Rosen, A., Shaltiel, R.: Constant-round oblivious transfer in the bounded storage model. J. Cryptol. 20, 165–202 (2007)MathSciNetCrossRef

[DSDCPY98]

De Santis, A., Di Crescenzo, G., Persiano, G., Yung, M.: Image density is complete for non-interactive-SZK. In: Larsen, K.G., Skyum, S., Winskel, G. (eds.) ICALP 1998. LNCS, vol. 1443, pp. 784–795. Springer, Heidelberg (1998). https://doi.org/10.1007/BFb0055102CrossRef

[GKR15]

Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. J. ACM 62(4), 27:1–27:64 (2015)

[GMR98]

Gennaro, R., Micciancio, T., Rabin, D.: An efficient non-interactive statistical zero-knowledge proof system for quasi-safe prime products. In: 5th ACM Conference on Computer and Communication Security (CCS’98), pp. 67–72, San Francisco, California, November 1998. ACM, ACM Press (1998)

[GMW91]

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)MathSciNetCrossRef

[GO94]

Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. J. Cryptol. 7(1), 1–32 (1994). https://doi.org/10.1007/BF00195207MathSciNetCrossRef

[Gol18]

Goldreich, O.: On doubly-efficient interactive proof systems. Found. Trends Theor. Comput. Sci. 13(3), 158–246 (2018)MathSciNetCrossRef

[GR17]

Gur, T., Rothblum, R.D.: A hierarchy theorem for interactive proofs of proximity. In: Papadimitriou, C.H. (ed.) 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, January 9-11, 2017, Berkeley, CA, USA, vol. 67, LIPIcs, pp. 39:1–39:43. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2017)

[GSV99]

Goldreich, O., Sahai, A., Vadhan, S.: Can statistical zero knowledge be made non-interactive? or on the relationship of SZK and NISZK. In: Wiener, M. (ed.) CRYPTO 1999. LNCS, vol. 1666, pp. 467–484. Springer, Heidelberg (1999). https://doi.org/10.1007/3-540-48405-1_30CrossRef

[HVW23]

Hazay, C., Venkitasubramaniam, M., Weiss, M.: Beyond MPC-in-the-head: black-box constructions of short zero-knowledge proofs. In: Rothblum, G., Wee, H. (eds.) TCC 2023. LNCS, vol. 14369, pp. 3–33. Springer, Cham (2023). https://doi.org/10.1007/978-3-031-48615-9_1CrossRef

[IKOS09]

Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput. 39(3), 1121–1152 (2009)MathSciNetCrossRef

[IOS97]

Itoh, T., Ohta, Y., Shizuya, H.: A language-dependent cryptographic primitive. J. Cryptol. 10(1), 37–49 (1997). https://doi.org/10.1007/s001459900018MathSciNetCrossRef

[Kil92]

Kilian, J.: A note on efficient zero-knowledge proofs and arguments (extended abstract). In: Kosaraju, S.R., Fellows, M., Wigderson, A., Ellis, A.J. (eds.) Proceedings of the 24th Annual ACM Symposium on Theory of Computing, May 4-6, 1992, Victoria, British Columbia, Canada, pp. 723–732. ACM (1992)

[KRR+20]

Kaslasi, I., Rothblum, G.N., Rothblum, R.D., Sealfon, A., Vasudevan, P.N.: Batch verification for statistical zero knowledge proofs. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12551, pp. 139–167. Springer, Cham (2020). https://doi.org/10.1007/978-3-030-64378-2_6CrossRef

[KRV21]

Kaslasi, I., Rothblum, R.D., Vasudevanr, P.N.: Public-coin statistical zero-knowledge batch verification against malicious verifiers. In: Canteaut, A., Standaert, F.-X. (eds.) EUROCRYPT 2021. LNCS, vol. 12698, pp. 219–246. Springer, Cham (2021). https://doi.org/10.1007/978-3-030-77883-5_8CrossRef

[MNRV24]

Mu, C., Nassar, S., Rothblum, R., Vasudevan, P.N.: Strong batching for non-interactive statistical zero-knowledge. Electron. Colloquium Comput. Complex. TR24–024 (2024)

[NOVY98]

Naor, M., Ostrovsky, R., Venkatesan, R., Yung, M.: Perfect zero-knowledge arguments for NP using any one-way permutation. J. Cryptol. 11, 87–108 (1998)MathSciNetCrossRef

[NV06]

Nguyen, M.-H., Vadhan, S.: Zero knowledge with efficient provers. In: Proceedings of the Thirty-Eighth Annual ACM Symposium on Theory of Computing, pp. 287–295 (2006)

[OV08]

Ong, S.J., Vadhan, S.: An equivalence between zero knowledge and commitments. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 482–500. Springer, Heidelberg (2008). https://doi.org/10.1007/978-3-540-78524-8_27CrossRef

[RR20]

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_5CrossRef

[RRR18]

Reingold, O., Rothblum, G.N., Rothblum, R.D.: Efficient batch verification for UP. In: Servedio, R.A. (eds.) 33rd Computational Complexity Conference, CCC 2018, June 22–24, 2018, San Diego, CA, USA, volume 102 of LIPIcs, pp. 22:1–22:23. Schloss Dagstuhl - Leibniz-Zentrum für Informatik (2018)

[RRR21]

Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. SIAM J. Comput. 50(3) (2021)

[RVW13]

Rothblum, G.N., Vadhan, S.P., Wigderson, A.: Interactive proofs of proximity: delegating computation in sublinear time. In: Boneh, D., Roughgarden, T., Feigenbaum, J., (eds.) Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, pp. 793–802. ACM (2013)

[RW04]

Renner, R., Wolf, S.: Smooth Rényi entropy and applications. In: International Symposium on Information Theory, 2004. ISIT 2004. Proceedings, p. 233. IEEE (2004)

Title: Doubly-Efficient Batch Verification in Statistical Zero-Knowledge
Authors: Or Keret
Ron D. Rothblum
Prashant Nalini Vasudevan
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_13

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"