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
Advances and Open Problems in Federated Learning
Kairouz, P., & McMahan, H. B. (2021) · Foundations and Trends in Machine Learning · doi:10.1561/2200000083 · Cited by 7,772
“Succinct non-interactive zero-knowledge proofs (SNARKs) [65] are a type of ZKP that provides constant proof size and verification that depends only on the input size, linearly.”
BackgroundZerocash: Decentralized Anonymous Payments from Bitcoin
Ben Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., & Virza, M. (2014) · 2014 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2014.36 · Cited by 1,925
“While knowledge-of-exponent assumptions are fairly strong, there is evidence that such assumptions may be inherent for constructing zk-SNARKs [24, 25].”
BackgroundSelf-citationOn the Size of Pairing-Based Non-interactive Arguments
Groth, J. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-49896-5_11 · Cited by 1,271
“Gentry and Wichs [GW11] showed that SNARGs must necessarily rely on non-falsifiable assumptions, and Bitansky et al. [BCCT12] proved designated verifier SNARKs exist if and only if extractable collision-resistant hash functions exist.”
BackgroundBulletproofs: Short Proofs for Confidential Transactions and More
Bunz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., & Maxwell, G. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00020 · Cited by 1,154
“Zero-knowledge SNARKs have been the subject of extensive research [Gro10,BCCT12,GGPR13, BCCT13,PHGR16,BSCG ` 13,Gro16].”
BackgroundSecurity and Privacy on Blockchain
Zhang, R., Xue, R., & Liu, L. (2020) · ACM Computing Surveys · doi:10.1145/3316481 · Cited by 959
“Another variation is the zero-knowledge Succinct Non-interactive ARgument of Knowledge (zk-SNARK) proof, introduced in 2012 by Bitansky and his coauthors [16] and is served as the backbone of the Zcash protocol [82].”
BackgroundOn-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption
López-Alt, A., Tromer, E., & Vaikuntanathan, V. (2012) · Proceedings of the forty-fourth annual ACM symposium on Theory of computing · doi:10.1145/2213977.2214086 · Cited by 910
Self-citationQuadratic Span Programs and Succinct NIZKs without PCPs
Gennaro, R., Gentry, C., Parno, B., & Raykova, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-38348-9_37 · Cited by 724
“Recent work [8, 19, 26] (see also [17]) has improved Micali’s construction by removing the random oracle, which is known to be uninstantiable [15], and replacing it with an “extractable collision-resistant hash function” (ECRH), whose security relies on the plausible, but non-falsifiable [37], assumption that for any…”
BackgroundResultSNARKs for C: Verifying Program Executions Succinctly and in Zero Knowledge
Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., & Virza, M. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40084-1_6 · Cited by 598
Self-citationA Survey of Machine Unlearning
Nguyen, T. T., Huynh, T. T., Ren, Z., Nguyen, P. L., Liew, A. W.-C., Yin, H., & Nguyen, Q. V. H. (2025) · ACM Transactions on Intelligent Systems and Technology · doi:10.1145/3749987 · Cited by 164
“2 implies the zero difference in the distribution of weights, i.e., 𝑃𝑟 ( 𝑤 ) = 𝑃𝑟 ( 𝑤 ) , where the 𝑟 ( 𝑟 ) and 𝑤 𝑢 are the parameters of the models given by 𝑈 ( .”
Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE
Asharov, G., Jain, A., López-Alt, A., Tromer, E., Vaikuntanathan, V., & Wichs, D. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-29011-4_29 · Cited by 454
“Such non-interactive proofs are known to exist in the random-oracle model or under strong assumptions [27,7,20,14].”
BackgroundSelf-citationFunctional Signatures and Pseudorandom Functions
Boyle, E., Goldwasser, S., & Ivan, I. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-54631-0_29 · Cited by 384
How to Delegate and Verify in Public: Verifiable Computation from Attribute-Based Encryption
Parno, B., Raykova, M., & Vaikuntanathan, V. (2012) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-28914-9_24 · Cited by 355
“A notable difference are approached based on PCPs [4] [14] [15] that may require a single offline stage for input processing and then allow multiple function evaluations.”
BackgroundMethodInfluentialEfficient Zero-Knowledge Arguments for Arithmetic Circuits in the Discrete Log Setting
Bootle, J., Cerulli, A., Chaidos, P., Groth, J., & Petit, C. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-49896-5_12 · Cited by 325
“An exciting line of research [22, 30, 6, 13, 7, 34, 4, 5, 24] has developed many proposals for succinct non-interactive arguments (SNARGs) yielding pairingbased constructions where the arguments consist of a constant number of group elements.”
BackgroundRecursive composition and bootstrapping for SNARKS and proof-carrying data
Bitansky, N., Canetti, R., Chiesa, A., & Tromer, E. (2013) · Proceedings of the forty-fifth annual ACM symposium on Theory of Computing · doi:10.1145/2488608.2488623 · Cited by 304
Self-citationSpartan: Efficient and General-Purpose zkSNARKs Without Trusted Setup
Setty, S. (2020) · Lecture Notes in Computer Science · doi:10.1007/978-3-030-56877-1_25 · Cited by 262
“Micali [73] made a similar protocol non-interactive in the random oracle model, thereby obtaining the first zero-knowledge succinct noninteractive argument of knowledge (zkSNARK) [26, 51].”
BackgroundSuccinct Non-interactive Arguments via Linear Interactive Proofs
Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., & Ostrovsky, R. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-36594-2_18 · Cited by 274
Self-citationBen-Sasson, E., Chiesa, A., & Spooner, N. (2016) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-53644-5_2 · Cited by 252
Self-citationDoubly-Efficient zkSNARKs Without Trusted Setup
Wahby, R. S., Tzialla, I., Shelat, A., Thaler, J., & Walfish, M. (2018) · 2018 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2018.00060 · Cited by 276
“Our protocol is public coin; we compile it into Hyrax, a zero-knowledge succinct non-interactive argument of knowledge (zkSNARK) [20] in the random oracle model [7], via the FiatShamir heuristic [41] (§7).”
MethodLeveled Fully Homomorphic Signatures from Standard Lattices
Gorbunov, S., Vaikuntanathan, V., & Wichs, D. (2015) · Proceedings of the forty-seventh annual ACM symposium on Theory of Computing · doi:10.1145/2746539.2746576 · Cited by 248
“There is a very simple construction of fully homomorphic signatures by relying on CS-Proofs [Mic94] or, more generally, succinct non-interactive arguments of knowledge for NP (SNARKs) [BCCT12, BCCT13, BCI + 13, GGPR13, PHGR13, BSCG + 13].”
MethodDelegating Computation: Interactive Proofs for Muggles
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2015) · Journal of the ACM · doi:10.1145/2699436 · Cited by 216
XCLAIM: Trustless, Interoperable, Cryptocurrency-Backed Assets
Zamyatin, A., Harz, D., Lind, J., Panayiotou, P., Gervais, A., & Knottenbelt, W. (2019) · 2019 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2019.00085 · Cited by 231
“The former can in theory be achieved by using non-interactive zero-knowledge proof (ZKP) systems such as SNARKs [39], STARKs [36] or Bulletproofs [45] for hash pre-image verifi-cation (assuming the corresponding arithmetic circuits can be efficiently constructed).”
BackgroundEfficiently Verifiable Computation on Encrypted Data
Fiore, D., Gennaro, R., & Pastro, V. (2014) · Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/2660267.2660366 · Cited by 231
“Several implementational efforts [24,54,55,59,49,11,60] show that also in this area we are on the verge of achieving practical efficiency, with the quadratic span program techniques of [27,49] showing particular promise.”
BackgroundOn or Off the Blockchain? Insights on Off-Chaining Computation and Data
Eberhardt, J., & Tai, S. (2017) · Lecture Notes in Computer Science · doi:10.1007/978-3-319-67262-5_1 · Cited by 210
“For that, non-interactive zero-knowledge proofs, more specifically zero-knowledge Succinct Non-interactive ARgument of Knowledge (zkSNARKs), can be employed [11, 8].”
Cryptographic primitives in blockchains
Wang, L., Shen, X., Li, J., Shao, J., & Yang, Y. (2019) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2018.11.003 · Cited by 209
Signatures of Correct Computation
Papamanthou, C., Shi, E., & Tamassia, R. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-36594-2_13 · Cited by 188
“Second, while achieving adaptive security appears relatively easy for univariate polynomial evaluation [23], achieving adaptive security in the multivariate case appears to be fundamentally more difficult.”
BackgroundSoK: Communication Across Distributed Ledgers
Zamyatin, A., Al-Bassam, M., Zindros, D., Kokoris-Kogias, E., Moreno-Sanchez, P., Kiayias, A., & Knottenbelt, W. J. (2021) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-64331-0_1 · Cited by 185
“SNARKs [45], STARKs [37] or Bulletproofs [54].”
Verifiable delegation of computation on outsourced data
Backes, M., Fiore, D., & Reischuk, R. M. (2013) · Proceedings of the 2013 ACM SIGSAC conference on Computer & communications security - CCS '13 · doi:10.1145/2508859.2516681 · Cited by 193
“, in SNARG-based approaches [12,28] and in signatures of correct computation [43]), or, otherwise, to send D to the server all at once (rather than sending it over time) and to keep a small local state which would not allow to append additional data at a later time (e.”
BackgroundScalable Zero Knowledge via Cycles of Elliptic Curves
Ben-Sasson, E., Chiesa, A., Tromer, E., & Virza, M. (2014) · Lecture Notes in Computer Science · doi:10.1007/978-3-662-44381-1_16 · Cited by 189
Self-citationvSQL: Verifying Arbitrary SQL Queries over Dynamic Outsourced Databases
Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., & Papamanthou, C. (2017) · 2017 IEEE Symposium on Security and Privacy (SP) · doi:10.1109/sp.2017.43 · Cited by 170
“State-of-the-art systems [10], [51], [26], [52], [57] can handle arbitrary non-deterministic arithmetic circuits by relying on succinct arguments of knowledge (SNARKs) [14], [32].”
BackgroundTime-Optimal Interactive Proofs for Circuit Evaluation
Thaler, J. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-40084-1_5 · Cited by 183
“As short PCPs are often a bottleneck in the development of efficient argument systems, other works have focused on avoiding their use [3,6,7,19].”
BackgroundFully Homomorphic Message Authenticators
Gennaro, R., & Wichs, D. (2013) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-42045-0_16 · Cited by 166
LegoSNARK: Modular Design and Composition of Succinct Zero-Knowledge Proofs
Campanelli, M., Fiore, D., & Querol, A. (2019) · Proceedings of the 2019 ACM SIGSAC Conference on Computer and Communications Security · doi:10.1145/3319535.3339820 · Cited by 160
“Some zero-knowledge proof systems—called succinct or simply zkSNARKs, zero-knowledge Succinct Non-interactive Argument of Knowledge—have short and efficiently verifiable proofs [15, 32, 53].”
BackgroundMethodSecurity and Privacy for Healthcare Blockchains
Zhang, R., Xue, R., & Liu, L. (2021) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2021.3085913 · Cited by 187
Verifying computations with state
Braun, B., Feldman, A. J., Ren, Z., Setty, S., Blumberg, A. J., & Walfish, M. (2013) · Proceedings of the Twenty-Fourth ACM Symposium on Operating Systems Principles · doi:10.1145/2517349.2522733 · Cited by 167
“Of course, Pantry’s general approach is known [11, 15, 32, 41].”
BackgroundMethodInfluentialPolyShard: Coded Sharding Achieves Linearly Scaling Efficiency and Security Simultaneously
Li, S., Yu, M., Yang, C.-S., Avestimehr, A. S., Kannan, S., & Viswanath, P. (2020) · IEEE International Symposium on Information Theory (ISIT) · doi:10.1109/isit44484.2020.9174305 · Cited by 167
Constant-round interactive proofs for delegating computation
Reingold, O., Rothblum, G. N., & Rothblum, R. D. (2016) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2897518.2897652 · Cited by 166
Self-Sovereign Identity: A Systematic Review, Mapping and Taxonomy
Schardong, F., & Custódio, R. F. (2022) · Sensors · doi:10.3390/s22155641 · Cited by 191
“Similarly, [117] uses zero-knowledge Succinct Non-interactive ARguments of Knowledge (zk-SNARK) [185] to create a VP format where holders can prove possession of a specific attribute and reveal its value.”
MethodHyperPlonk: Plonk with Linear-Time Prover and High-Degree Custom Gates
Chen, B., Bünz, B., Boneh, D., & Zhang, Z. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-30617-4_17 · Cited by 163
“Modern SNARKs are constructed by compiling an information-theoretic object called an Interactive Oracle Proof (IOP) [11] to a SNARK using a suitable cryptographic commitment scheme.”
InfluentialGabay, D., Akkaya, K., & Cebe, M. (2020) · IEEE Transactions on Vehicular Technology · doi:10.1109/tvt.2020.2977361 · Cited by 153
“In this way, the privacy of the person submitting the information is protected. zkSNARKs [10] is an efficient variant of zero-knowledge proofs that allows the prover to prove his/her knowledge in a single message.”
BackgroundMethodNova: Recursive Zero-Knowledge Arguments from Folding Schemes
Kothapalli, A., Setty, S., & Tzialla, I. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-15985-5_13 · Cited by 152
“SNARKs for NP [7, 23, 24, 29, 36] trivially imply a folding scheme for NP : given two NP instances u 1 and u 2 and the corresponding witnesses, the prover proves u 1 by producing a SNARK.”
A Survey and Comparison of Post-Quantum and Quantum Blockchains
Yang, Z., Alfauri, H., Farkiani, B., Jain, R. K., Pietro, R. D., & Erbad, A. (2023) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2023.3325761 · Cited by 179
“There are two popular schemes of non-interactive ZKPs: zero-knowledge scalable transparent arguments of knowledge (zk-STARKs) [124] and zero-knowledge succinct non-interactive argument of knowledge (zk-SNARKs) [125].”
BackgroundSecure Sampling of Public Parameters for Succinct Zero Knowledge Proofs
Ben-Sasson, E., Chiesa, A., Green, M., Tromer, E., & Virza, M. (2015) · 2015 IEEE Symposium on Security and Privacy · doi:10.1109/sp.2015.25 · Cited by 131
“In preprocessing zk-SNARKs, the complexity of sampling public parameters grows with the size of the computation being proved [17]– [31]; in fully-succinct zk-SNARKs, that complexity is independent of computation size [14], [16], [32]–[40].”
BackgroundSelf-citationEfficient RAM and Control Flow in Verifiable Outsourced Computation
Wahby, R. S., Setty, S., Ren, Z., Blumberg, A. J., & Walfish, M. (2015) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2015.23097 · Cited by 141
“…and many of the prior systems (including BCTV, Pantry, and Pinocchio [62]) handle a more general problem—a zero-knowledge proof of knowledge [21, 40]—in which the prover can supply inputs to the computation and keep them private (for example, a private database for which the verifier knows a…”
BackgroundMethodPractical Homomorphic MACs for Arithmetic Circuits
Catalano, D., & Fiore, D. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-38348-9_21 · Cited by 148
“The problem of realizing homomorphic signatures can be solved in theory using Succinct Noninteractive Arguments of Knowledge (SNARKs) [8].”
BackgroundSuccinct Randomized Encodings and their Applications
Bitansky, N., Garg, S., Lin, H., Pass, R., & Telang, S. (2015) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2746539.2746574 · Cited by 152
“Previous publicly-verifiable schemes relied on strong knowledge assumptions [34, 12, 21, 13] or proven secure only in the random oracle model [43].”
BackgroundSelf-citationZero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs
Boneh, D., Boyle, E., Corrigan-Gibbs, H., Gilboa, N., & Ishai, Y. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-26954-8_3 · Cited by 160
“Different kinds of linear PCPs were used, either explicitly or implicitly, in the vast literature on succinct arguments for NP (see [24,25,27,31,51,57,60,70,77,79, 80,85,88] and references therein).”
MethodSecure Two-Party Computation with Low Communication
Damgård, I., Faust, S., & Hazay, C. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-28914-9_4 · Cited by 131
How to delegate computations: the power of no-signaling proofs
Kalai, Y. T., Raz, R., & Rothblum, R. D. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591809 · Cited by 120
Bitansky, N., Canetti, R., Chiesa, A., Goldwasser, S., Lin, H., Rubinstein, A., & Tromer, E. (2016) · Journal of Cryptology · doi:10.1007/s00145-016-9241-9 · Cited by 143
Self-citationA Survey on Blockchain Scalability: From Hardware to Layer-Two Protocols
Rebello, G. A. F., Camilo, G. F., de Souza, L. A. C., Potop-Butucaru, M., de Amorim, M. D., Campista, M. E. M., & Costa, L. H. M. K. (2024) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2024.3376252 · Cited by 130
“There are two leading technologies used to compute zero-knowledge proofs in blockchain-based systems: Zero-Knowledge Succinct Non-interactive ARgument of Knowledge (ZK-SNARK) [249] and Zero-Knowledge Scalable Transparent ARgument of Knowledge (ZK-STARK) [75].”
Brakedown: Linear-Time and Field-Agnostic SNARKs for R1CS
Golovnev, A., Lee, J. L. C., Setty, S., Thaler, J., & Wahby, R. S. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38545-2_7 · Cited by 111
“A SNARK [57, 66, 45, 18] is a cryptographic primitive that enables a prover to prove to a verifier the knowledge of a satisfying witness to an NP statement by producing a proof π such that the size of π and the cost to verify it are both sub-linear in the size of the witness.”
BackgroundSubvector Commitments with Application to Succinct Arguments
Lai, R. W. F., & Malavolta, G. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-26948-7_19 · Cited by 107
“[16], a SNARK verifier is a Turing machine with runtime logarithmic in that of the corresponding NP verifier.”
MethodOn the existence of extractable one-way functions
Bitansky, N., Canetti, R., Paneth, O., & Rosen, A. (2014) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2591796.2591859 · Cited by 116
“the uniform distribution, required in [7].”
BackgroundMethodInfluentialSelf-citationIntegriDB: Verifiable SQL for Outsourced Databases
Zhang, Y., Katz, J. I., & Papamanthou, C. (2015) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2810103.2813711 · Cited by 97
“Security of our ASO also relies on an extractability assumption [6], which is inherited from [11].”
BackgroundLipmaa, H. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-42033-7_3 · Cited by 109
“We only mention that one can construct a related zap [8], and a related (public or designatedverifier) succinct non-interactive argument of knowledge (SNARK, see [22,6]) by using the techniques of [1,14].”
MethodADSNARK: Nearly Practical and Privacy-Preserving Proofs on Authenticated Data
Backes, M., Barbosa, M., Fiore, D., & Reischuk, R. M. (2015) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2015.24 · Cited by 108
Laconic Oblivious Transfer and Its Applications
Cho, C., Döttling, N., Garg, S., Gupta, D., Miao, P., & Polychroniadou, A. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-63715-0_2 · Cited by 102
Non-Interactive Zero-Knowledge Proofs for Composite Statements
Agrawal, S., Ganesh, C., & Mohassel, P. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-96878-0_22 · Cited by 103
“Starting with the construction of Kilian [Kil92] based on probabilistically checkable proofs (PCPs), made non-interactive by Micali [Mic00], there has been further works [GLR11, BCCT12, DFH12] that construct succinct arguments by removing interaction in Kilian’s PCP-based protocol.”
MethodZeeStar: Private Smart Contracts by Homomorphic Encryption and Zero-knowledge Proofs
Steffen, S., Bichsel, B., Baumgartner, R., & Vechev, M. (2022) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46214.2022.9833732 · Cited by 107
“Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) [12, 18, 19] are generic NIZK proof constructions supporting any arithmetic circuit φ and featuring constant-cost proof verification in the size of φ (plus a typically negligible linear cost in the size of x).”
BackgroundSubversion-Zero-Knowledge SNARKs
Fuchsbauer, G. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-76578-5_11 · Cited by 107
“All previous bilinear-group-based SNARKs are proven under strong cryptographic assumptions ( knowledge assumptions), for which there is evidence that they might be unavoidable [GW11, BCCT12].”
BackgroundRevocable Quantum Timed-Release Encryption
Unruh, D. (2015) · Journal of the ACM · doi:10.1145/2817206 · Cited by 110
“At least for our constructions (see below), this could be achieved as follows: The client produces a commitment c on the content of the classical inner TRE V 0 and proves that c contains the right content (using a SNARK [4] so that the verification time does not depend on T ).”
BackgroundPhotoProof: Cryptographic Image Authentication for Any Set of Permissible Transformations
Naveh, A., & Tromer, E. (2016) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2016.23 · Cited by 102
“SNARK constructions are known, and some are implemented, on the basis of knowledge-of-exponent assumptions [25], [35], [10], [43], [6], [4], [22] and extractable collision resistant hashes [8], [39], [10].”
BackgroundSelf-citationNon-Interactive Zero-Knowledge for Blockchain: A Survey
Partala, J., Nguyen, T., & Pirttikangas, S. (2020) · IEEE Access · doi:10.1109/access.2020.3046025 · Cited by 103
Xing, Z., Zhang, Z., Zhang, Z., Li, Z., Li, M., Liu, J., Zhang, Z., Zhao, Y., Sun, Q., Zhu, L., et al. (2025) · IEEE Communications Surveys & Tutorials · doi:10.1109/comst.2025.3561657 · Cited by 107
“To verify the correct execution of the detection mechanism at the server, zk-SNARK proofs, PERCHs [180] are generated by the server, allowing any client to verify the model removal and aggregation.”
Revocable Quantum Timed-Release Encryption
Unruh, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-55220-5_8 · Cited by 102
zkay: Specifying and Enforcing Data Privacy in Smart Contracts
Steffen, S., Bichsel, B., Gersbach, M., Melchior, N., Tsankov, P., & Vechev, M. (2019) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3319535.3363222 · Cited by 109
“Practical NIZK proof constructions have been proposed [6, 11, 27, 42] and made available in Ethereum [16, 23].”
Sub-linear Lattice-Based Zero-Knowledge Arguments for Arithmetic Circuits
Baum, C., Bootle, J., Cerulli, A., del Pino, R., Groth, J., & Lyubashevsky, V. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-96881-0_23 · Cited by 82
“Schnorr [Sch91] An exciting line of research [Gro10a, Lip12, BCCT12, GGPR13, BCCT13, PHGR13, Gro16] on succinct non-interactive arguments (SNARGs) has yielded pairing-based constructions where the arguments consist of a constant number of group elements.”
BackgroundChosen-Ciphertext Secure Fully Homomorphic Encryption
Canetti, R., Raghuraman, S., Richelson, S., & Vaikuntanathan, V. (2017) · Lecture notes in computer science · doi:10.1007/978-3-662-54388-7_8 · Cited by 85
Self-citationLunar: A Toolbox for More Efficient Universal and Updatable zkSNARKs and Commit-and-Prove Extensions
Campanelli, M., Faonio, A., Fiore, D., Querol, A., & Rodríguez, H. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-92078-4_1 · Cited by 89
Batch Arguments for $$\textsf{NP}$$ and More from Standard Bilinear Group Assumptions
Waters, B. R., & Wu, D. J. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-15979-4_15 · Cited by 77
Wahrstätter, A., Ernstberger, J., Yaish, A., Zhou, L., Qin, K., Tsuchiya, T., Steinhorst, S., Svetinović, D., Christin, N., Barczentewicz, M., et al. (2024) · International World Wide Web Conference (WWW) · doi:10.1145/3589334.3645431 · Cited by 105
“This is achieved by relying on Zero-Knowledge Succinct NonInteractive Argument of Knowledge (zk-SNARKS) [6].”
MethodScalable Zero Knowledge Via Cycles of Elliptic Curves
Ben‐Sasson, E., Chiesa, A., Tromer, E., & Virza, M. (2016) · Algorithmica · doi:10.1007/s00453-016-0221-0 · Cited by 93
“For instance, if the adversary is allowed any auxiliary input (perhaps even by way of maliciously chosen circuits C), extraction may be difficult because the auxiliary input may encode an obfuscated strategy [7]; such intuition can in fact be formalized to yield limitations to extractability [16].”
BackgroundSelf-citationLinear-Time Zero-Knowledge Proofs for Arithmetic Circuit Satisfiability
Bootle, J., Cerulli, A., Ghadafi, E., Groth, J., Hajiabadi, M., & Jakobsen, S. K. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70700-6_12 · Cited by 87
Halo Infinite: Proof-Carrying Data from Additive Polynomial Commitments
Boneh, D., Drake, J., Fisch, B., & Gabizon, A. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-84242-0_23 · Cited by 74
Public-Coin Differing-Inputs Obfuscation and Its Applications
Ishai, Y., Pandey, O., & Sahai, A. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46497-7_26 · Cited by 80
Themis: Fast, Strong Order-Fairness in Byzantine Consensus
Kelkar, M., Deb, S., Long, S., Juels, A., & Kannan, S. (2023) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3576915.3616658 · Cited by 73
“This is particularly notable since we find that other fair-ordering protocols cannot easily be made op-timistically O( 𝑛 ) even using SNARKs.”
MethodInfluentialBen‐Sasson, E., Chiesa, A., Genkin, D., & Tromer, E. (2013) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2422436.2422481 · Cited by 84
“All known PCP-based succinct argument constructions [61, 71, 5, 30, 22, 14, 29, 47] inherit these problem representations.”
BackgroundSelf-citationNon-interactive delegation and batch NP verification from standard computational assumptions
Brakerski, Z., Holmgren, J., & Kalai, Y. T. (2017) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3055399.3055497 · Cited by 76
“Despite their strong assumptions, all of the aforementioned schemes except [35] require two messages, and the only non-interactive schemes, prior to this work, relied on knowledge assumptions [9].”
BackgroundWahby, R. S., Howald, M., Garg, S., Shelat, A. A., & Walfish, M. (2016) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2016.51 · Cited by 79
Lattice-Based SNARGs and Their Application to More Efficient Obfuscation
Boneh, D., Ishai, Y., Sahai, A., & Wu, D. J. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-56617-7_9 · Cited by 73
“All of the schemes can be converted into an argument of knowledge (i.e., a SNARK)—in some cases, this requires a stronger cryptographic assumption. where the overall prover complexity is Õ(s)), while maintaining quasi-optimal succinctness.”
BackgroundMethodInfluentialNon-interactive Batch Arguments for NP from Standard Assumptions
Choudhuri, A. R., Jain, A., & Jin, Z. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-84259-8_14 · Cited by 66
“Since verifying the membership of k NP instances is itself an NP problem, BARGs with poly-logarithmic communication can be obtained from succinct non-interactive arguments (SNARGs) for NP [3,4,18,28,44].”
vRAM: Faster Verifiable RAM with Program-Independent Preprocessing
Zhang, Y., Genkin, D., Katz, J. I., Papadopoulos, D., & Papamanthou, C. (2018) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2018.00013 · Cited by 85
Arya: Nearly Linear-Time Zero-Knowledge Proofs for Correct Program Execution
Bootle, J., Cerulli, A., Groth, J., Jakobsen, S., & Maller, M. (2018) · Lecture notes in computer science · doi:10.1007/978-3-030-03326-2_20 · Cited by 76
GZKP: A GPU Accelerated Zero-Knowledge Proof System
Ma, W., Xiong, Q., Shi, X., Ma, X., Jin, H., Kuang, H., Gao, M., Zhang, Y., Shen, H., & Hu, W. (2023) · International Conference on Architectural Support for Programming Languages and Operating Systems (ASPLOS) · doi:10.1145/3575693.3575711 · Cited by 87
“Recently, many works [2, 3, 5, 6, 9, 34, 39, 51, 54, 57, 60] have made lots of efforts to optimize the zkSNARK protocol and make it more practical.”
BackgroundWalshe, M., Epiphaniou, G., Al‐Khateeb, H., Hammoudeh, M. A. A., Katos, V., & Dehghantanha, A. (2019) · Ad Hoc Networks · doi:10.1016/j.adhoc.2019.101988 · Cited by 69
“The potential to increase privacy and security using ZKP has been recently exploited in blockchain applications using a modified version of Di Crescenzo and Lipmaa’s protocol in [40] .”
MethodPrivacy-Preserving Identity Management System on Blockchain Using Zk-SNARK
Luong, D. A., & Park, J. H. (2023) · IEEE Access · doi:10.1109/access.2022.3233828 · Cited by 75
“Therefore, there must be a method for the IP to verify a user’s IAs and issue the user a certificate without knowing the user’s PS. Anonymous authentication using zk-SNARK [3] is a good solution to this problem.”
MethodApon, D., Katz, J. I., Shi, E., & Thiruvengadam, A. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-54631-0_8 · Cited by 72
On the concrete efficiency of probabilistically-checkable proofs
Ben‐Sasson, E., Chiesa, A., Genkin, D., & Tromer, E. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488681 · Cited by 76
“Recursive composition and bootstrapping for SNARKs and proof-carrying data.”
BackgroundMethodInfluentialSelf-citationA Survey of Machine Unlearning
Nguyen, T. T., Huynh, T. T., Ren, Z., Nguyen, P. L., Liew, A. W.-C., Yin, H., & Nguyen, Q. V. H. (2022) · arXiv · doi:10.48550/arxiv.2209.02299 · Cited by 193
“2 implies the zero difference in the distribution of weights, i.e., 𝑃𝑟 ( 𝑤 ) = 𝑃𝑟 ( 𝑤 ) , where the 𝑟 ( 𝑟 ) and 𝑤 𝑢 are the parameters of the models given by 𝑈 ( .”
Secure Data Sharing over Vehicular Networks Based on Multi-sharding Blockchain
Huang, J., Kong, L., Wang, J., Chen, G., Jian-hua, G., Huang, G., & Khan, M. K. (2023) · ACM Transactions on Sensor Networks · doi:10.1145/3579035 · Cited by 69
“One of the most popular ZKP schemes is Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK) [3].”
BackgroundMaesa, D. D. F., Lisi, A., Mori, P., Ricci, L., & Boschi, G. (2023) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2022.103577 · Cited by 69
Rate-1 Non-Interactive Arguments for Batch-NP and Applications
Devadas, L., Goyal, R., Kalai, Y. T., & Vaikuntanathan, V. (2022) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs54457.2022.00103 · Cited by 59
“[3], [4], [5], [6], [7], [8], to name a few).”
Kalai, Y. T., Raz, R., & Rothblum, R. D. (2013) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2488608.2488679 · Cited by 59
Full Accounting for Verifiable Outsourcing
Wahby, R. S., Ji, Y., Blumberg, A. J., Shelat, A. A., Thaler, J., Walfish, M., & Wies, T. (2017) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3133956.3133984 · Cited by 75
“Another line of work uses argument protocols, both interactive [73–75] and non-interactive [14, 21, 26, 47, 56, 66] (“SNARK” refers to the latter).”
BackgroundInfluentialAn Introduction to the Use of zk-SNARKs in Blockchains
Pinto, A. M. (2020) · Springer proceedings in business and economics · doi:10.1007/978-3-030-37110-4_16 · Cited by 73
Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
Choudhuri, A. R., Hubáček, P., Kamath, C., Pietrzak, K., Rosen, A., & Rothblum, G. N. (2019) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3313276.3316400 · Cited by 65
Rinocchio: SNARKs for Ring Arithmetic
Ganesh, C., Nitulescu, A., & Soria-Vázquez, E. (2023) · Journal of Cryptology · doi:10.1007/s00145-023-09481-3 · Cited by 58
Lattice-Based zk-SNARKs from Square Span Programs
Gennaro, R., Minelli, M., Nitulescu, A., & Orrù, M. (2018) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3243734.3243845 · Cited by 70
“So far all known practical SNARKs rely on “classical” pre-quantum assumptions 4 .”
BackgroundInfluentialHandcrafted Backdoors in Deep Neural Networks
Hong, S., Carlini, N., & Kurakin, A. (2022) · neural information processing systems · doi:10.52202/068431-0586 · Cited by 118
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.