From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again
The DOI matches its Crossref record; 77 of the 77 references it cites were found in a registry or an index.
Abstract
The existence of succinct non-interactive arguments for NP (i.e., non-interactive computationally-sound proofs where the verifier's work is essentially independent of the complexity of the NP nondeterministic verifier) has been an intriguing question for the past two decades. Other than CS proofs in the random oracle model [Micali, FOCS '94], the only existing candidate construction is based on an elaborate assumption that is tailored to a specific protocol [Di Crescenzo and Lipmaa, CiE '08].
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Claims other papers make about this one
Each is checked against this paper’s own text: does it say what the citing paper says it does?
In the citing paper
“Other platforms include [125] focused on a range of medical applications and [321] for enterprise use cases.”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [321]
In the citing paper
“- IBM Federated Learning [321] is a Python-based federated learning framework for enterprise environments, which provides a basic fabric for adding advanced features.”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [321]
In the citing paper
“- IBM Federated Learning [321] is a Python-based federated learning framework for enterprise environments, which provides a basic fabric for adding advanced features.”
From Advances and Open Problems in Federated Learning (2021) · cites this paper as [321]
Citations
Cites
Fully homomorphic encryption using ideal lattices
Gentry, C. (2009) · Proceedings of the forty-first annual ACM symposium on Theory of computing · doi:10.1145/1536414.1536440 · Cited by 6,806
How To Prove Yourself: Practical Solutions to Identification and Signature Problems
Fiat, A., & Shamir, A. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-47721-7_12 · Cited by 3,943
Universally composable security: a new paradigm for cryptographic protocols
Canetti, R. (2001) · Proceedings 42nd IEEE Symposium on Foundations of Computer Science · doi:10.1109/sfcs.2001.959888 · Cited by 3,309
Self-citationThe knowledge complexity of interactive proof systems
Goldwasser, S., Micali, S., & Rackoff, C. (1989) · SIAM Journal on Computing · doi:10.1137/0218012 · Cited by 3,285
On lattices, learning with errors, random linear codes, and cryptography
Regev, O. (2005) · Proceedings of the thirty-seventh annual ACM symposium on Theory of computing · doi:10.1145/1060590.1060603 · Cited by 2,313
Merkle, R. C. (2007) · Lecture Notes in Computer Science · doi:10.1007/0-387-34805-0_21 · Cited by 1,691
A Pseudorandom Generator from any One-way Function
HÅstad, J., Impagliazzo, R., Levin, L. A., & Luby, M. (1999) · SIAM Journal on Computing · doi:10.1137/s0097539793244708 · Cited by 1,653
Efficient Fully Homomorphic Encryption from (Standard) LWE
Brakerski, Z., & Vaikuntanathan, V. (2011) · 2011 IEEE 52nd Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2011.12 · Cited by 1,449
Generating hard instances of lattice problems (extended abstract)
Ajtai, M. (1996) · Proceedings of the twenty-eighth annual ACM symposium on Theory of computing - STOC '96 · doi:10.1145/237814.237838 · Cited by 1,405
Lower Bounds for Discrete Logarithms and Related Problems
Shoup, V. (1997) · Lecture Notes in Computer Science · doi:10.1007/3-540-69053-0_18 · Cited by 1,229
Research works printed but not linked: 16
- 10.5555/1760749.1760759 · doi:10.5555/1760749.1760759
- 10.5555/646253.686344 · doi:10.5555/646253.686344
- 10.5555/1880918.1880936 · doi:10.5555/1880918.1880936
- 10.1137/070709244 · doi:10.1137/070709244 · Paper page
- 10.5555/2033036.2033046 · doi:10.5555/2033036.2033046
- 10.5555/1756123.1756163 · doi:10.5555/1756123.1756163
- 10.5555/1881412.1881446 · doi:10.5555/1881412.1881446
- 10.5555/646756.759582 · doi:10.5555/646756.759582
- 10.5555/3088723.3088762 · doi:10.5555/3088723.3088762
- 10.5555/1788414.1788417 · doi:10.5555/1788414.1788417
- 10.5555/1881412.1881445 · doi:10.5555/1881412.1881445
- 10.5555/1894302.1894327 · doi:10.5555/1894302.1894327
- 10.5555/646763.706338 · doi:10.5555/646763.706338
- 10.5555/646754.705190 · doi:10.5555/646754.705190
- 10.5555/1754542.1754568 · doi:10.5555/1754542.1754568
- 10.5555/1802614.1802616 · doi:10.5555/1802614.1802616
Cited by
Items 501–544 of 544
Enhancing Decentralized Privacy : A Systematic Review of Techniques for Permissionless Blockchain
Saaninkoski, S. (2024) · Tampere University Institutional Repository (Tampere University) · Cited by 1
Trustworthy Federated Learning With Authenticated ZKPs in Mobile Edge Intelligence
Li, Z., Chen, X., Sun, Q., Lu, Y., Li, D., Zhang, J., & Ai, B. (2026) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2026.3670154
“ThezkSNARK technique [31] is a state-of-the-art ZKP technique to authenticate FL models.”
Kouyem, A. K. (2023) · MOnAMi (Hochschule Mittweida Hochschulbibliothek)
Liu, X., & Wu, Y. (2025) · IEEE International Conference on Information, Communication and Networks (ICICN) · doi:10.1109/icicn67355.2025.11430435
“…relies on trusted setup and has high computational overhead, making it difficult to meet the high-real-time requirements of the industrial Internet [9]. zk-STARK improves transparency by eliminating trusted setup, but its large proof volume and communication overhead limit its application in…”
Development of Optimized Operations for Homomorphic Cryptography
Bon, N. (2025) · HAL
Verifiability and accountability in the Cloud
Azraoui, M. (2016) · theses.fr (ABES) · doi:10.70675/d64f1ee5zecfdz4aa2zab87z9611a23442c1
Verifiable Computation and Biometric Authentication
Keuffer, J. (2019) · theses.fr (ABES) · doi:10.70675/e3abb3c0z74dbz418ezaeb7z56b053911cf9
Un recueil de SNARKs : sécurité quantique, extractabilité et confidentialité des données
Nitulescu, A. (2019) · theses.fr (ABES) · doi:10.70675/613f26dez1fcfz4bb3zb710ze245a8b88a2a · Cited by 2
Non-interactive arguments of knowledge
Orrù, M. (2020) · theses.fr (ABES) · doi:10.70675/d240a5f6zc24dz43abz8b31zc586e211ca8e
Payment Channel Networks with Resource-constrained Devices
Rebello, G. A. F. (2023) · theses.fr (ABES) · doi:10.70675/78b910bcz49c8z4241z95a2z0e9953c35ad3
Protocoles d’attestation dans les environnements dynamiques
Jacques, T. (2024) · theses.fr (ABES) · doi:10.70675/54ab3524zafc6z4520z86f7z5836d04073ba
Analysis of AES-based and arithmetization-oriented symmetric cryptography primitives
Bariant, A. (2024) · theses.fr (ABES) · doi:10.70675/91e98fcezfe0cz4b88z8e64zb2a679034ecd · Cited by 2
On scaling-up online multi-agent multi-task assignment
Nedelmann, D. C. (2024) · theses.fr (ABES) · doi:10.70675/bc9e0533z7737z4874z84b6z06616d3f3aaa
The Phantom Thread Between Malleable and Non-Malleable Cryptography
Russo, L. (2025) · theses.fr (ABES) · doi:10.70675/a794b49ez69b5z4e89z8619zfbe754ad9170
Privacy-preserving and fully distributed identity management systems
Gestin, M. (2024) · theses.fr (ABES) · doi:10.70675/a3baa27ez3be9z485cz8141z3441ade018ce · Cited by 1
Hardiansyah, M. A. B. A. A. (2026) · Indonesian Journal of Education (INJOE) · doi:10.5281/zenodo.19493874
Polynomial Commitment Schemes from Classical Constructions to Post-Quantum Directions
Iavich, M., Kuchukhidze, T., & Bocu, R. (2026) · Cryptography · doi:10.3390/cryptography10020027
“By confirming complex program execution in milliseconds at little expense, these technologies offer private and verifiable computing [4,5].”
A Witness Encryption for Quadratic Arithmetic Programs
Chang, T.-H., Wu, Y.-C., Liu, Z.-Y., Hsu, J.-C., Tso, R., & Mambo, M. (2026) · Lecture notes in computer science · doi:10.1007/978-981-95-8034-7_28
Cirrus: Performant and Accountable Distributed SNARK
Wang, W., Shi, F., Vilardell, D., & Zhang, F. (2026) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2026.240668
“Succinct Non-interactive Arguments of Knowledge (SNARKs) [1]–[11] enable efficient, non-interactive verification of computations.”
Efficient encrypted network traffic management with zero-knowledge proof
Zhang, N. (2026) · Cybersecurity · doi:10.1186/s42400-025-00517-8
Extended Review of Polynomial Commitments
Iavich, M., Kuchukhidze, T., & Bocu, R. (2026) · Lecture notes on data engineering and communications technologies · doi:10.1007/978-3-032-23341-7_14
Özcan, A. Ş., Tezcan, C., & Savaş, E. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-27574-5_19
Lavanya, B., & S.Janani (2026) · Cureus Journal of Computer Science. · doi:10.7759/s44389-026-00110-1
zkSAS: Practical Zero-Knowledge Proofs for Verifiable Spectrum Access Management
Purbasha, N. F., Alom, I., Burger, E. W., Hou, Y. T., Lou, W., & Xiao, Y. (2026) · IEEE International Symposium on Dynamic Spectrum Access Networks · doi:10.1109/dyspan69846.2026.11571163
“Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARK) [17] is a type of ZKP system specifically designed for efficiently proving the validity of a computation.”
DNaaS: Towards Scalable and Trusted Time-Sensitive Networks
Amet, M., Thomas, L., & Song, Y. (2026) · IEEE Conference on Computer Communications (INFOCOM) · doi:10.1109/infocom59046.2026.11571313
“Zero-knowledge protocols [23], [24] allow a prover to prove to a verifier the knowledge of some data that meets some properties without sharing the data.”
Mutable Batch Arguments and Applications
Goyal, R. (2026) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2026.101
LendLocked: Privacy & Transparency for Digital Library Lending
Wang, B., Hall, P., & Park, S. (2026) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2026-0111
Practice-Oriented Instances of Deterministic LPN
Cid, C., Davidson, A., & Phanse, A. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-32560-0_14
GAPP: Generic Aggregation of Polynomial IOPs
Ganesh, C., Patranabis, S., Prakash, S., & Singh, N. K. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-35424-2_12
Golden: Lightweight Non-interactive Distributed Key Generation
Bünz, B., Choi, K., & Komlo, C. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-35374-0_8
“While a generic zkSNARK (zero-knowledge succinct non-interactive argument of knowledge) system [8] could be used to prove R eVRF † , we prove it using Bulletproofs [15] (see Section 3.4).”
InfluentialZero-Knowledge Cloud Analytics
Zhu, Z. P., Lam, C., Frolov, A., Miers, I., & Liu, Z. (2026) · ACM SIGCOMM Conference (SIGCOMM) · doi:10.1145/3789240.3829157
Post-quantum Internet Key Exchange via Authenticated Forward-Secure KEM
Zhao, Y., Zhou, B., Zhao, Z., Dong, Y., Huang, C., & Jiang, H. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-35428-0_9
Guo, S., Guan, R., Qi, J., Zhang, Z., Duan, T., Wang, S., Wu, Y., & Cui, H. (2026) · IEEE International Conference on Data Engineering (ICDE) · doi:10.1109/icde65706.2026.00155
“A popular type of NIZKP is zero-knowledge succinct non-interactive arguments of knowledge (zkSNARK) [49], [50], which allows any arithmetic circuit ϕ and guarantees constant-cost proof verification in the size of ϕ , making it suitable for blockchain applications [18], [51], [52].”
Auditable Certificate Issuance with Zero-Knowledge Proof of Claim Validation
Abe, R., Inagaki, R., & Suzuki, S. (2026) · IEEE Annual International Computer Software and Applications Conference (COMPSAC) · doi:10.1109/compsac69091.2026.00299
“In particular, ZK-SNARK is a scheme to prove that the prover knows an input that satisfies a statement [9].”
Accountable Fair Exchange Protocols on Blockchain
Mochizuki, R., Abe, R., & Suzuki, S. (2026) · IEEE Annual International Computer Software and Applications Conference (COMPSAC) · doi:10.1109/compsac69091.2026.00132
“A succinct non-interactive argument of knowledge (SNARK) [27] enables non-interactive and efficiently verifiable proofs; Practical in-stantiations include Groth16 [28].”
Constructions for Multi-Party Computation Based on Secret Sharing and Homomorphic Encryption
Lu, Y. (2024) · Institutional Repositories DataBase (IRDB)
Leš, D. (2026) · University of Maribor digital library (University of Maribor)
Overview on Blockchain for Accountability in Social Media Content Moderation
Maggio, F., Michienzi, A., & Guidi, B. (2026) · International Conference on Information Technology for Social Good (GoodIT) · doi:10.1145/3794786.3830758
A SNARK for (Non-)Subsequences with Text-Sub-Linear Proving Time
Fiore, D., Ling, S., Tang, K. H., Tran, H. H., Wang, H., & Yan, Y. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-38708-0_1
Rothmann, T. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-38708-0_9
PhotoMT : Accelerating Zero-Knowledge Proofs with a Photonic-Electronic Merkle Tree Engine
Xu, Y., Li, M., Li, S., Zhang, Z., & Li, K. (2026) · ACM/IEEE Design Automation Conference (DAC) · doi:10.1145/3770743.3804306
On the use of ECDSA with hierarchical public key delegation in identity-based scenarios
Cardoso, L., & Junior, M. A. S. (2026) · IACR Communications in Cryptology · doi:10.62056/an2i89krz
Multi-hop Functional Encryption
Datta, P., Guan, J., Korb, A., & Sahai, A. (2026) · Lecture notes in computer science · doi:10.1007/978-3-032-43630-6_18
TeleSparse: Practical Privacy-Preserving Verification of Deep Neural Networks
Maheri, M. M., Haddadi, H., & Davidson, A. (2025) · arXiv · doi:10.48550/arxiv.2504.19274
“In pursuit of this objective, we utilize ZK-SNARK [8], a cryptographic protocol that enables Prover 𝑃 to generate a proof 𝜋 .”
Metadata
- Authors
- Bitansky, N., Canetti, R., Chiesa, A., & Tromer, E.
- Affiliations
- Tel Aviv University (IL)
- Boston University (US)
- MIT Computer Science and Artificial Intelligence Laboratory (US)
- Venue
- Proceedings of the 3rd Innovations in Theoretical Computer Science Conference
- Publisher
- ACM
- Published
- 2012-01-08
- Pages
- 326-349
- OpenAlex
- W2166670067
- Cited by
- 493
- References
- 77
- Citations by year
- 2026: 29 · 2025: 48 · 2024: 60 · 2023: 48 · 2022: 42 · 2021: 36 · 2020: 30 · 2019: 34 · 2018: 21 · 2017: 23 · 2016: 25 · 2015: 18 · 2014: 31 · 2013: 34 · 2012: 13
- FWCI
- 23.55
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- Conference on Innovations in Theoretical Computer Science (publishedVersion)
- Funders
- Seventh Framework Programme (240258)
- Topics
- Physical Sciences › Computer Science › Computer Networks and Communications › Cryptography and Data Security
- Physical Sciences › Computer Science › Computer Networks and Communications › Advanced Authentication Protocols Security
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Complexity and Algorithms in Graphs
- Keywords
- succinct non-interactive arguments of knowledge, computational soundness, random oracle model, brevity
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.