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 201–300 of 544
Equational Security Proofs of Oblivious Transfer Protocols
Li, B., & Micciancio, D. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-76578-5_18 · Cited by 18
Exploring Constructions of Compact NIZKs from Various Assumptions
Katsumata, S., Nishimaki, R., Yamada, S., & Yamakawa, T. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-26954-8_21 · Cited by 18
“4 They have been the subject of extensive research, e.g., [45,62,8,33,63,28,72,47], where constructions are known to exist either in the random oracle model or based on non-falsifiable assumptions.”
BackgroundePoSt: Practical and Client-Friendly Proof of Storage-Time
Zhang, C., Li, X., & Au, M. H. (2023) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2022.3233780 · Cited by 16
“5) Optimizing Our ePoSt : We implement ePoSt using zk - SNARK [19].”
MethodNyato, E. J., Kimito, E. C., Yang, J., Lee, D., & Lee, D. (2024) · Automation in Construction · doi:10.1016/j.autcon.2024.105825 · Cited by 18
Zero-Knowledge Location Privacy via Accurate Floating-Point SNARKs
Ernstberger, J., Zhang, C., Ciprian, L., Jovanovic, P., & Steinhorst, S. (2025) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp61157.2025.00057 · Cited by 22
“A zero-knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK) [28] is a cryptographic protocol, where a prover P convinces a verifier V that a certain NP-statement is true, without disclosing any information besides the veracity of the statement.”
Qi, H., Cheng, Y., Xu, M., Yu, D., Wang, H., & Lyu, W. (2023) · IEEE Transactions on Computers · doi:10.1109/tc.2023.3235975 · Cited by 16
On Constant-Round Concurrent Zero-Knowledge from a Knowledge Assumption
Gupta, D., & Sahai, A. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-13039-2_5 · Cited by 16
Limits of Extractability Assumptions with Distributional Auxiliary Input.Preprint
Boyle, E., & Pass, R. (2013) · IACR Cryptology ePrint Archive · Cited by 32
Fully Succinct Batch Arguments for $$\textsf{NP}$$ from Indistinguishability Obfuscation
Garg, R., Sheridan, K., Waters, B. R., & Wu, D. J. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-22318-1_19 · Cited by 15
Multikey Fully Homomorphic Encryption and Applications
López-Alt, A., Tromer, E., & Vaikuntanathan, V. (2017) · SIAM Journal on Computing · doi:10.1137/14100124x · Cited by 15
Self-citationKuhn, C., Hofheinz, D., Rupp, A., & Strufe, T. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-92075-3_20 · Cited by 15
Privacy-Preserving and Publicly Verifiable Matrix Multiplication
Liu, J., & Zhang, L. F. (2022) · IEEE Transactions on Services Computing · doi:10.1109/tsc.2022.3215499 · Cited by 15
“There are many existing proposals [7], [33], [34], [35] for securely outsourcing computations to a cloud.”
BackgroundZero-Knowledge Middleboxes.Preprint
Grubbs, P., Arun, A., Zhang, Y., Bonneau, J., & Walfish, M. (2021) · IACR Cryptology ePrint Archive · Cited by 29
Harmonia: Securing Cross-Chain Applications Using Zero-Knowledge ProofsPreprint
Belchior, R., Dimov, D., Karadjov, Z., Pfannschmidt, J., Vasconcelos, A., & Correia, M. P. (2023) · doi:10.36227/techrxiv.170327806.66007684/v1 · Cited by 15
LVMT: An Efficient Authenticated Storage for Blockchain
Li, C., Beillahi, S. M., Yang, G. Y., Wu, M., Xu, W., & Long, F. (2024) · ACM Transactions on Storage · doi:10.1145/3664818 · Cited by 14
Real-World Universal zkSNARKs are Non-Malleable
Faonio, A., Fiore, D., & Russo, L. (2024) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3658644.3690351 · Cited by 14
“A notable class of zero-knowledge proofs are zkSNARKs (zero-knowledge succinct non-interactive arguments of knowledge) [Mic94,BCCT12] in which, after an initial setup phase, the prover can generate proofs that are short and easy to verify, without the need of any interaction.”
Mangrove: A Scalable Framework for Folding-Based SNARKs
Nguyen, W., Datta, T., Chen, B., Tyagi, N., & Boneh, D. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-68403-6_10 · Cited by 17
Incentive mechanism design via smart contract in blockchain-based edge-assisted crowdsensing
Ying, C., Jin, H., Li, J., Si, X., & Luo, Y. (2024) · Frontiers of Computer Science · doi:10.1007/s11704-024-3542-1 · Cited by 16
Feneuil, T., & Rivain, M. (2025) · Journal of Cryptology · doi:10.1007/s00145-025-09543-8 · Cited by 14
“While not providing (asymptotically) succinct proofs like SNARKs [BCCT12, Gro16], the MPCitH paradigm is particularly efficient for small circuits such as those involved to construct (post-quantum) signature schemes.”
A Pure Indistinguishability Obfuscation Approach to Adaptively-Sound SNARGs for $$\textsf{NP}$$
Waters, B. R., & Wu, D. J. (2025) · Lecture notes in computer science · doi:10.1007/978-3-032-01907-3_10 · Cited by 14
Lattice-Based Zero-Knowledge SNARGs for Arithmetic Circuits
Nitulescu, A. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-30530-7_11 · Cited by 14
“This is the same encoding used to construct lattice-based SNARKs in [20], a slight variation of the classical LWE cryptosystem initially presented by Regev [40] and later extended in [14].”
BackgroundInfluentialTransparency Dictionaries with Succinct Proofs of Correct Operation
Tzialla, I., Kothapalli, A., Parno, B. J., & Setty, S. (2022) · Network and Distributed System Security Symposium · doi:10.14722/ndss.2022.23143 · Cited by 25
“For our purpose, SNARKs enable proving the correct execution of (stateful) computations, since those executions can be represented with NP statements (a formal definition of SNARKs is elsewhere [15, 30]).”
BackgroundGabay, D., Akkaya, K., & Cebe, M. (2019) · IEEE LCN Symposium on Emerging Topics in Networking (LCN Symposium) · doi:10.1109/lcnsymposium47956.2019.9000682 · Cited by 14
“zkSNARKs [10] is an efficient variant of zeroknowledge proofs that allows the prover to prove his knowledge in a single message.”
BackgroundMethodCo-Utile Peer-to-Peer Decentralized Computing
Domingo‐Ferrer, J., Blanco-Justicia, A., Sánchez, D., & Jebreel, N. (2020) · IEEE/ACM International Symposium on Cluster, Cloud and Grid Computing (CCGrid) · doi:10.1109/ccgrid49817.2020.00-90 · Cited by 19
“Also in recent years, succinct non-interactive arguments (SNARGs) and succinct non-interactive arguments of knowledge (SNARKs) have been introduced to allow verification of NP statements with much reduced complexity [4], [1].”
BackgroundTowards dependable and trustworthy outsourced computing: A comprehensive survey and tutorial
Zhao, M., Hu, C., Song, X., & Zhao, C. (2019) · Journal of Network and Computer Applications · doi:10.1016/j.jnca.2019.01.021 · Cited by 14
Lenstra, A. K., Kleinjung, T., & Thomé, E. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-42001-6_9 · Cited by 13
Simultaneous Amplification: The Case of Non-interactive Zero-Knowledge
Goyal, V., Jain, A., & Sahai, A. (2019) · Lecture notes in computer science · doi:10.1007/978-3-030-26951-7_21 · Cited by 13
“Yet, despite much effort, NIZK is unfortunately known from very few assumptions: [19, 17, 18, 35, 6, 5, 13, 8, 32].”
BackgroundOrbweaver: Succinct Linear Functional Commitments from Lattices
Fisch, B., Liu, Z., & Vesely, P. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38545-2_4 · Cited by 13
VP2-Match: Verifiable Privacy-Aware and Personalized Crowdsourcing Task Matching via Blockchain
Wu, H., Düdder, B., Jiang, S., & Wang, L. (2024) · IEEE Transactions on Mobile Computing · doi:10.1109/tmc.2024.3369085 · Cited by 13
“Additionally, the corresponding accumulation values acc ( S iP ) , i ∈ [2 , 6] are derived with S iP , pk , and a random number r iP as input.”
BackgroundMethodZero Knowledge Contingent Payments for Trained Neural Networks
Zhou, Z., Cao, X., Liu, J., Zhang, B., & Ren, K. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-88428-4_31 · Cited by 13
Smart, N. P. (2023) · IEEE Security & Privacy · doi:10.1109/msec.2023.3279517 · Cited by 13
A Black-Box Construction of a CCA2 Encryption Scheme from a Plaintext Aware (sPA1) Encryption Scheme
Dachman-Soled, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-54631-0_3 · Cited by 13
“This type of assumption is known as a knowledge assumption (other examples of knowledge assumptions include the knowledge of exponent assumption [18,3] and extractable collision resistant hash functions [6]) and is thus a non-falsifiable assumption.”
BackgroundPrimitives towards verifiable computation: a survey
Ahmad, H., Wang, L., Hong, H., Li, J., Dawood, H., Ahmed, M., & Yang, Y. (2018) · Frontiers of Computer Science · doi:10.1007/s11704-016-6148-4 · Cited by 17
DIV: Resolving the Dynamic Issues of Zero-knowledge Set Membership Proof in the Blockchain
Xu, Z., & Chen, L. (2021) · ACM SIGMOD International Conference on Management of Data (SIGMOD) · doi:10.1145/3448016.3457248 · Cited by 16
“, correctness of digital signatures [51]), the technique called SNARK [13] is proposed.”
MethodInfluentialKRAKEN: A Secure, Trusted, Regulatory-Compliant, and Privacy-Preserving Data Sharing Platform
Gabrielli, S., Krenn, S., Pellegrino, D., Baún, J. C. P., Berganza, P. P., Ramacher, S., & Vandevelde, W. (2022) · Springer eBooks · doi:10.1007/978-3-030-98636-0_6 · Cited by 13
Is blockchain a cure for peer-to-peer lending?
Yan, W., & Zhou, W. (2022) · Annals of Operations Research · doi:10.1007/s10479-022-05108-1 · Cited by 13
“In addition to the above two techniques, “zk-Snarks” (Bitansky et al., 2012), a variation of zero-knowledge proof, is adopted by a cryptocurrency named Zcash (ZEC).”
MethodAggregation of Gamma-Signatures and Applications to Bitcoin.Preprint
Zhao, Y. (2018) · IACR Cryptology ePrint Archive · Cited by 13
On the Security of Optimistic Blockchain Mechanisms *Preprint
Li, J. (2023) · SSRN Electronic Journal · doi:10.2139/ssrn.4499357 · Cited by 26
Verifiable Coded Computation of Multiple Functions
Kim, W., Kruglik, S., & Kiah, H. M. (2024) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2024.3450288 · Cited by 12
“This breakthrough triggered a flurry of results in verifiable computations [21]–[24].”
BackgroundOn the Connection between Leakage Tolerance and Adaptive Security
Nielsen, J. B., Venturi, D., & Zottarel, A. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36362-7_30 · Cited by 12
“In fact, the only constructions of SNARGs we know of are either based on the random oracle model of Bellare and Rogaway [4] (as shows Micali [37] by applying the Fiat-Shamir transform [26] to Kilian’s protocol) or under so-called “knowledge of exponent” assumptions [5].”
BackgroundMethodMulti-Input Functional Encryption.
Goldwasser, S., Goyal, V., Jain, A., & Sahai, A. (2013) · Cited by 12
Li, W., Meese, C., Nejad, M., & Guo, H. (2021) · International Conference on Hot Information-Centric Networking (HotICN) · doi:10.1109/hoticn53262.2021.9680829 · Cited by 12
Hardware acceleration of number theoretic transform for zk‐SNARK
Zhao, H., Ding, D., Wang, F., Hua, P., Wang, N., Wu, Q., & Chai, Z. (2023) · Engineering Reports · doi:10.1002/eng2.12639 · Cited by 15
“Zk-SNARK (zero-knowledge Succinct Non-interactive Arguments of Knowledge) [6]–[8], a class of ZKP protocols, is used to generate short, fixed-length proofs for complex programs and provide fast verification, improving the usability of ZKP in real-world applications.”
MethodPrivacy-Preserving and Trustless Verifiable Fairness Audit of Machine Learning Models
Tang, G., Tan, W., & Cai, M. (2023) · International Journal of Advanced Computer Science and Applications · doi:10.14569/ijacsa.2023.0140294 · Cited by 17
“The popular zero knowledge proof notions used in practice are zero-knowledge succinct non-interactive arguments of knowledge (zkSNARKs, for short) [23]–[25].”
BackgroundNon-interactive Zero-Knowledge from Non-interactive Batch Arguments
Champion, J., & Wu, D. J. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38545-2_2 · Cited by 13
Formal Verification of Zero-Knowledge Circuits
Coglio, A., McCarthy, E., & Smith, E. W. (2023) · Electronic Proceedings in Theoretical Computer Science · doi:10.4204/eptcs.393.9 · Cited by 13
“Spurred by recent advances that have greatly improved their efficiency [9, 23, 14, 7, 13], zero-knowledge proofs are finding increasingly wide application, particularly in the blockchain world [20, 32, 8, 19, 12, 1], holding promise to rebalance privacy on the Internet [37, 18].”
BackgroundBatch verifiable computation of outsourced functions
Zhang, L. F., & Safavi–Naini, R. (2015) · Designs Codes and Cryptography · doi:10.1007/s10623-015-0092-4 · Cited by 12
“The SNARGs or SNARKs of [4,13] give non-interactive schemes for delegating computations.”
How to Construct a Leakage-Resilient (Stateless) Trusted Party
Genkin, D., Ishai, Y., & Weiss, M. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70503-3_7 · Cited by 12
“While there are efficient ZK protocols without hardware (including non-interactive zero-knowledge protocols (NIZKs) [21,35], or succinct non-interactive arguments of knowledge (SNARKs) [5]), such protocols do not (and cannot) have the last two features of TP-based solutions.”
BackgroundHuman Privacy in Virtual and Physical Worlds: Multidisciplinary Perspectives
Lacity, M. C., & Coon, L. L. (2024) · Technology, work and globalization · doi:10.1007/978-3-031-51063-2 · Cited by 14
The Bottleneck Complexity of Secure Multiparty Computation
Boyle, E., Jain, A., Prabhakaran, M., & Yu, C.-H. (2018) · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · doi:10.4230/lipics.icalp.2018.24 · Cited by 11
Multiparty Computation with Low Communication, Computation and Interaction via Threshold FHE.Preprint
Asharov, G., Jain, A., & Wichs, D. (2011) · IACR Cryptology ePrint Archive · Cited by 30
A decentralized and trustless e-voting system based on blockchain technology
Golnarian, D., Saedi, K., & Bahrak, B. (2022) · International Computer Conference, Computer Society of Iran (CSICC) · doi:10.1109/csicc55295.2022.9780507 · Cited by 11
Efficient Zero-Knowledge Proof Systems
Bootle, J., Cerulli, A., Chaidos, P., & Groth, J. (2016) · Lecture notes in computer science · doi:10.1007/978-3-319-43005-8_1 · Cited by 20
Mariani, J., Perešíni, M., & Homoliak, I. (2025) · arXiv (Cornell University) · doi:10.48550/arxiv.2504.20296 · Cited by 11
“Succinct arguments originate with Bitansky et al. [9] and were applied to anonymous currency in Zerocoin [48].”
Probability Models of Distributed Proof Generation for zk-SNARK-Based Blockchains
Bespalov, Y., Garoffolo, A., Kovalchuk, L., Nelasa, H., & Oliynykov, R. (2021) · Mathematics · doi:10.3390/math9233016 · Cited by 10
“For the first time term “zk-SNARK” itself was introduced in [18], based on [19].”
BackgroundGuo, C., You, L., & Hu, G. (2022) · Security and Communication Networks · doi:10.1155/2022/2791058 · Cited by 10
Efficiency of Zero-Knowledge Proofs: A Through Review and Analysis
Sah, C. P., Kaur, M., & Singh, G. (2024) · IEEE International Conference on Public Key Infrastructure and its Applications (PKIA) · doi:10.1109/pkia62599.2024.10729195 · Cited by 14
“SNARKs is a subclass of NIZKPs that takes efficiency to the next level, achieving impressive succinctness and scalability, making them a promising tool for various applications in blockchain and decentralized systems used in real life [9, 10, 14, 15, 16, 17, 18, 19, 20, 21, 22]”
MethodEfficient Authenticated Multi-Pattern Matching
Zhou, Z. G., Zhang, T., Chow, S. S. M., Zhang, Y., & Zhang, K. (2016) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/2897845.2897906 · Cited by 10
“General-purpose techniques for verifiable computation [19, 9, 10, 20, 11, 15] and their implementations [30, 29] are potential solutions to the problem.”
BackgroundA Fully Decentralized Infrastructure for Subscription-based IoT Data Trading
Lin, C.-H. V., Huang, C., Yuan, Y.-H., & Yuan, Z. (2020) · International Congress on Blockchain and Applications · doi:10.1109/blockchain50366.2020.00027 · Cited by 9
“Therefore, it is worth exploring the usage of the non-interactive zero-knowledge protocol such as zk-SNARKS [21] which can generate proofs off-chain and simplify the verification process.”
BackgroundComposition with Knowledge Assumptions
Kerber, T., Kiayias, A., & Kohlweiss, M. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-84259-8_13 · Cited by 10
“Proving these primitives’ security under composition would typically involve using one of a number of off-the-shelf compositional frameworks, such as Universal Composability [8] or Constructive Cryptography [31], specifying an ideal behaviour for the primitive, and constructing a simulator which coerces the ideal behav…”
InfluentialFiore, D., & Tucker, I. (2022) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3548606.3560630 · Cited by 10
“We recall the definition of (pre-processing) zero-knowledge succinct non-interactive arguments of knowledge (zkSNARK) [5, 6] with specializable universal structured reference string (SRS) [35].”
MethodTwo-Server Delegation of Computation on Label-Encrypted Data
Chen, X., & Zhang, L. F. (2019) · IEEE Transactions on Cloud Computing · doi:10.1109/tcc.2019.2913375 · Cited by 10
“The problem of enforcing server-side computations’ integrity has been extensively studied under the name of securely outsourcing computation and realized with verifiable computation [2], [9], [10], [11], homomorphic message authenticators [8], [13], [19], and many other primitives [3], [12], [16], [22].”
Samaritan: Linear-Time Prover SNARK from New Multilinear Polynomial Commitments
Ganesh, C., Patranabis, S., & Singh, N. K. (2025) · Lecture notes in computer science · doi:10.1007/978-981-95-5116-3_15 · Cited by 10
“Several early SNARKs [Gro10, Lip12, BCCT12, BCI + 13, GGPR13, PHGR13, BCG + 13, Lip13, BCTV14] with constant proof size and verification complexity are based on linear PCP compiled using a cryptographic tool like linear-only encodings (for instance, exponentiation in a bilinear group).”
A Black-Box Construction of a CCA2 Encryption Scheme from a Plaintext Aware Encryption Scheme.
Dachman-Soled, D. (2013) · Cited by 9
Balancing privacy and accountability in digital payment methods using zk-SNARKs
Bontekoe, T., Everts, M. H., & Peter, A. (2022) · Conference on Privacy, Security and Trust · doi:10.1109/pst55820.2022.9851987 · Cited by 9
Efficient Verifiable Differential Privacy with Input Authenticity in the Local and Shuffle Model
Bontekoe, T., Asghar, H. J., & Türkmen, F. (2025) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2025-0076 · Cited by 9
Generalized homomorphic MACs with efficient verification
Zhang, L. F., & Safavi–Naini, R. (2014) · ACM ASIA Public-Key Cryptography Workshop (APKC) · doi:10.1145/2600694.2600697 · Cited by 9
“The SNARKs of [7, 24] can realize homomorphic signatures with efficient verification.”
BackgroundOff-chain Execution and Verification of Computationally Intensive Smart Contracts
Sariboz, E., Kolachala, K., Panwar, G., Vishwanathan, R., & Misra, S. (2021) · IEEE International Conference on Blockchain and Cryptocurrency (ICBC) · doi:10.1109/icbc51069.2021.9461142 · Cited by 12
“Adoption of zk-SNARKs [26] to verify smart contracts was proposed by [27]; however, their solution requires that the application code be written in a domainspecific language that they designed.”
BackgroundProof-of-Possession for KEM Certificates using Verifiable Generation
Güneysu, T. E., Hodges, P., Land, G., Ounsworth, M., Stebila, D., & Zaverucha, G. (2022) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3548606.3560560 · Cited by 12
“Our MPCitH-based verifiable generation construction yields PoPs for this parameter regime at sizes as small as 79 kB and at 156 kB for a reasonable (𝑁, 𝜏) trade-off, which is comparable with zkSNARKs but not as good as MLWE- and MSIS-based ZK proofs.”
MethodInfluentialRevisiting Cycles of Pairing-Friendly Elliptic Curves
Bellés-Muñoz, M., Urroz, J. J., & Silva, J. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38545-2_1 · Cited by 9
“Succinct non-interactive arguments of knowledge (SNARKs) are of particular interest, since they provide a computationally sound proof of small size compared to the size of the statement [9].”
BackgroundVerifiable computation using multiple provers.Preprint
Blumberg, A. J., Thaler, J., Vu, V., & Walfish, M. (2014) · IACR Cryptology ePrint Archive · Cited by 31
Privacy and Compliance Design Options in Offline Central Bank Digital Currencies
Michalopoulos, P., Olowookere, O., Pocher, N., Sedlmeir, J., Veneris, A. G., & Puri, P. (2025) · IEEE Transactions on Network and Service Management · doi:10.1109/tnsm.2025.3575367 · Cited by 13
“A prominent example of general-purpose ZKPs is zk-SNARKs [54], which have the additional property of short (“succinct”) proofs and verification times.”
TeleSparse: Practical Privacy-Preserving Verification of Deep Neural Networks
Maheri, M. M., Haddadi, H., & Davidson, A. (2025) · Proceedings on Privacy Enhancing Technologies · doi:10.56553/popets-2025-0161 · Cited by 15
Hu, X., Zhou, W., Yin, J., Cheng, G., Yan, S., & Wu, H. (2023) · Peer-to-Peer Networking and Applications · doi:10.1007/s12083-023-01497-7 · Cited by 8
“In 2011, Nir Bitansky et al. [18] proposed zk-SNARK.”
BackgroundBlockchain-enhanced computer vision approach for remote safety inspection in construction
Kim, D., Yang, J., Lee, D., Lee, D., Rahimian, F. P., & Park, C. (2024) · Engineering Construction & Architectural Management · doi:10.1108/ecam-03-2024-0385 · Cited by 11
zk‐STARKs based scheme for sealed auctions in chains
Wei, L., Liang, P., & Fei, L. (2024) · IET Blockchain · doi:10.1049/blc2.12090 · Cited by 8
Toward RSA-OAEP Without Random Oracles
Cao, N., O’Neill, A., & Zaheri, M. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45374-9_10 · Cited by 8
“…for us here is a hierarchy of “extractability” notions we define and assume for the round functions, called EXT-RO, EXT0, EXT1, EXT2, roughly paralleling PA-RO, PA0, PA1, PA2 respectively, and generalizing prior work [26, 27, 34, 12], although we mention that [34] already has our EXT1 definition.”
BackgroundA Note on the Unsoundness of vnTinyRAM's SNARK.
Parno, B. J. (2015) · Cited by 8
zkSSI: A Zero-Knowledge-Based Self-Sovereign Identity Framework
Hoang, A.-T., Ileri, C. U., Sanders, W., & Schulte, S. (2024) · IEEE International Conference on Blockchain (Blockchain) · doi:10.1109/blockchain62396.2024.00043 · Cited by 7
“…is one of the most popular zero-knowledge-proving schemes used to prove the validity of a statement without revealing any sensitive information about it [4]. zk-SNARKs have been used with various proving systems (e.g., Groth16 [9], Plonk [10]) but their applications often follow common steps.”
BackgroundMethodRashid, A., Masood, A., & Abbas, H. (2020) · Future Generation Computer Systems · doi:10.1016/j.future.2020.10.021 · Cited by 8
Kim, S., Lee, H., & Seo, J. H. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-22966-4_14 · Cited by 8
“A lot of important research for succinct non-interactive argument (SNARG) [35, 44, 12, 33, 13, 47, 8, 11, 38, 37, 45, 32, 55, 25] have been proposed on the top of bilinear groups, where an argument consists of a constant number of group elements.”
BackgroundOn-Demand Device Authentication using Zero-Knowledge Proofs for Smart Systems
Zhong, Y., Hovanes, J., & Guin, U. (2023) · ACM Great Lakes Symposium on VLSI (GLSVLSI) · doi:10.1145/3583781.3590275 · Cited by 10
“It can be performed by proving to the verifier the knowledge of the preimage of a hash generated from collision-resistant and preimage-resistant hash algorithm [6].”
BackgroundZero-Knowledge Proofs and Privacy: A Technical Look at Privacy
Garimella, K. K., & Conway, D. (2024) · Technology, work and globalization · doi:10.1007/978-3-031-51063-2_8 · Cited by 9
VeriCNN: Integrity verification of large-scale CNN training process based on zk-SNARK
Fan, Y., Ma, K., Zhang, L., Liu, J., Xiong, N. N., & Yu, S. (2024) · Expert Systems with Applications · doi:10.1016/j.eswa.2024.124531 · Cited by 7
Spooky Interaction and Its Discontents: Compilers for Succinct Two-Message Argument Systems
Dwork, C., Naor, M., & Rothblum, G. N. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53015-3_5 · Cited by 8
A need to help: stories of emergent behaviour from the scene of accident
Kvarnlöf, L. (2018) · International Journal of Emergency Services · doi:10.1108/ijes-03-2017-0015 · Cited by 8
“Then he transforms this witness into a samplable form using probabilistically checkable proof (PCP) (Babai et al., 1991; Micali, 2000; Goldwasser et al., 2011; Bitansky et al., 2012; Canetti et al., 2013).”
BackgroundMethodCoded State Machine -- Scaling State Machine Execution under Byzantine Faults
Li, S., Sahraei, S., Yu, M., Avestimehr, S., Kannan, S., & Viswanath, P. (2019) · ACM Symposium on Principles of Distributed Computing (PODC) · doi:10.1145/3293611.3331573 · Cited by 8
“In order to scale throughput, there have been several existing proposals to do verifiable computing [5–7, 21, 38], where one node does computation and other nodes verify the computation in sub-linear time.”
BackgroundFlow: Separating Consensus and ComputePreprint
Hentschel, A., Shirley, D., & Lafrance, L. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1909.05821 · Cited by 7
“Potential solutions include zkSnarks [17], Bulletproofs [18], and TrueBit ’s approach [19].”
zkay v0.2: Practical Data Privacy for Smart ContractsPreprint
Baumann, N., Steffen, S., Bichsel, B., Tsankov, P., & Vechev, M. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.01020 · Cited by 11
“▷ Zk-SNARKs: An efficient instantiation of NIZKs [2].”
BackgroundBrakedown: Linear-time and post-quantum SNARKs for R1CS.Preprint
Golovnev, A., Lee, J. L. C., Setty, S., Thaler, J., & Wahby, R. S. (2021) · IACR Cryptology ePrint Archive · Cited by 7
Buldini, A., Mazzocca, C., Montanari, R., & Uluagac, A. S. (2025) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2025.3636051 · Cited by 6
“This concept led to significant advancements, including Zero-Knowledge Succinct Non-Interactive Arguments of Knowledge (zk-SNARK) [47], and Zero-Knowledge Scalable Transparent Arguments of Knowledge (zk-STARK) [48].”
Batch Verifiable Computation of Polynomials on Outsourced Data
Zhang, L. F., & Safavi–Naini, R. (2015) · Lecture notes in computer science · doi:10.1007/978-3-319-24177-7_9 · Cited by 6
The Uber-Knowledge Assumption: A Bridge to the AGM
Bauer, B., Farshim, P., Harasser, P., & Kohlweiss, M. (2024) · IACR Communications in Cryptology · doi:10.62056/anr-zoja5 · Cited by 6
MuxProofs: Succinct Arguments for Machine Computation from Vector Lookups
Di, Z., Xia, L., Nguyen, W., & Tyagi, N. (2024) · Lecture notes in computer science · doi:10.1007/978-981-96-0935-2_8 · Cited by 6
Nardelli, M., Sclavis, F. D., & Iezzi, M. (2026) · Distributed Ledger Technologies Research and Practice · doi:10.1145/3801555 · Cited by 6
Poster: Privacy-preserving Genome Analysis using Verifiable Off-Chain Computation
Visscher, L., Alghazwi, M., Karastoyanova, D., & Türkmen, F. (2022) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3548606.3563548 · Cited by 6
“The off-chain solution uses a rollup system that performs computations off-chain and generates a proof of correct computation using zk-SNARKs[3].”
MethodGENES: An Efficient Recursive zk-SNARK and Its Novel Application in Blockchain
Liu, J., Guo, L., & Kang, T. (2025) · Electronics · doi:10.3390/electronics14030492 · Cited by 10
Secure Computation from Millionaire
Shelat, A. A., & Venkitasubramaniam, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48797-6_30 · Cited by 7
“Although one might be able to use either Universal arguments [19, 3] or SNARKS [8, 5] to achieve malicious security with low communication, both of those techniques dramatically increase the computational overhead of the protocol.”
MethodSeet, J., & Griffin, P. (2019) · IEEE Asia-Pacific Conference on Computer Science and Data Engineering (CSDE) · doi:10.1109/csde48274.2019.9162386 · Cited by 6
Multi-server verifiable delegation of computations: Unconditional security and practical efficiency
Zhang, L. F. (2021) · Information and Computation · doi:10.1016/j.ic.2021.104740 · Cited by 6
“There are many emerging solutions [9, 15, 23, 24, 28] for verifying the cloud servers’ work.”
Background
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.