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 101–200 of 544
Handcrafted Backdoors in Deep Neural Networks
Hong, S., Carlini, N., & Kurakin, A. (2022) · neural information processing systems · doi:10.52202/068431-0586 · Cited by 120
Blockchain Based Zero-Knowledge Proof of Location in IoT
Wu, W., Liu, E., Gong, X., & Wang, R. (2020) · International Conference on Communications · doi:10.1109/icc40277.2020.9149366 · Cited by 56
“Zero-Knowledge Succinct Non-Interactive Argument of Knowledge (zk-SNARK) is a novel form of zero-knowledge cryptography which is introduced in [11] and built in [12].”
BackgroundSuccinct Arguments from Multi-prover Interactive Proofs and Their Efficiency Benefits
Bitansky, N., & Chiesa, A. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32009-5_16 · Cited by 64
Self-citationData-Driven Learning for Data Rights, Data Pricing, and Privacy Computing
Xu, J., Hong, N., Xu, Z., Zhao, Z., Wu, C., Kuang, K., Wang, J., Zhu, M., Zhou, J., Ren, K., et al. (2023) · Engineering · doi:10.1016/j.eng.2022.12.008 · Cited by 65
Verifiable Set Operations over Outsourced Databases
Canetti, R., Paneth, O., Papadopoulos, D., & Triandopoulos, N. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-54631-0_7 · Cited by 54
“Our construction of knowledge accumulators is very similar to previous construction of knowledge commitments in [6, 21].”
BackgroundMethodResultInfluentialSelf-citationHash First, Argue Later: Adaptive Verifiable Computations on Outsourced Data
Fiore, D., Fournet, C., Ghosh, E., Kohlweiss, M., Ohrimenko, O., & Parno, B. J. (2016) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2976749.2978368 · Cited by 69
“sumption can been seen as an n-Knowledge of Exponent Assumption [11] but for the general group model.”
BackgroundInfluentialhinTS: Threshold Signatures with Silent Setup
Garg, S., Jain, A., Mukherjee, P., Sinha, R., Wang, M., & Zhang, Y. (2024) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp54263.2024.00057 · Cited by 53
“To solve this dilemma, we require the aggregator to output a succinct non-interactive argument of knowledge (SNARK) [17], [16] that establishes the well-formedness of the aggregated public key.”
Cluster Computing in Zero Knowledge
Chiesa, A., Tromer, E., & Virza, M. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-46803-6_13 · Cited by 70
“, short and easy to verify [63]; these are known as zk-SNARKs [44, 12, 15].”
BackgroundSelf-citationThreshold Signatures with Private Accountability
Boneh, D., & Komlo, C. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-15985-5_19 · Cited by 58
“When using a zk-SNARK [13] for the proof system, the signature overhead over the underlying ATS signature is quite short; its length depends only on the security parameter.”
HyperNova: Recursive Arguments for Customizable Constraint Systems
Kothapalli, A., & Setty, S. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-68403-6_11 · Cited by 75
A Survey on Data Availability in Layer 2 Blockchain Rollups: Open Challenges and Future Improvements
Saif, M. B., Migliorini, S., & Spoto, F. (2024) · Future Internet · doi:10.3390/fi16090315 · Cited by 55
“The name zk-SNARK stays for Zero-Knowledge Succinct Non-Interactive Argument of Knowledge [15].”
Limits of Extractability Assumptions with Distributional Auxiliary Input
Boyle, E., & Pass, R. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48800-3_10 · Cited by 62
“Bitansky et al [5] made this idea more explicit: Given some candidate EOWF family F , consider the distribution ZF over auxiliary input formed by “obfuscating” a program Π(·) for uniformly chosen s, where Π(·) takes as input a function index e from the alleged EOWF family F = {fi}, applies a pseudorandom function (PRF…”
BackgroundResultInfluentialComputational Integrity with a Public Random String from Quasi-Linear PCPs
Ben‐Sasson, E., Bentov, I., Chiesa, A., Gabizon, A., Genkin, D., Hamilis, M., Pergament, E., Riabzev, M., Silberstein, M., Tromer, E., et al. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-56617-7_19 · Cited by 62
“SHA-3, via the Fiat-Shamir heuristic [39] (or via an extractable collision resistant hash function [27]).”
MethodSelf-citationEfficient Techniques for Publicly Verifiable Delegation of Computation
Elkhiyaoui, K., Önen, M., Azraoui, M., & Molva, R. A. (2016) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/2897845.2897910 · Cited by 48
“One of the most relevant applications of the SNARK approach [7] appears in Pinocchio [19].”
BackgroundOAKE: a new family of implicitly authenticated diffie-hellman protocols
Yao, A. C.-C., & Zhao, Y. (2013) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2508859.2516695 · Cited by 48
“black-box cryptography, and for achieving cryptographic schemes of conceptually simple structure and analysis, achieving cryptographic schemes based on non-black-box assumptions or primitives has been attracting much research attention recent years ([6, 20, 21, 37, 28, 13]).”
BackgroundAuthenticating Aggregate Queries over Set-Valued Data with Confidentiality
Xu, C. L., Chen, Q., Hu, H., Xu, J., & Hei, X. (2017) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2017.2773541 · Cited by 48
“In step (ii), h e ð(cid:6)Þ is an extractable collision resistant hash (ECRH) function that has one unique property— extractability [36].”
BackgroundMethodVerifiable and Provably Secure Machine Unlearning
Eisenhofer, T., Riepel, D., Chandrasekaran, V., Ghosh, E., Ohrimenko, O., & Papernot, N. (2025) · IEEE Conference on Secure and Trustworthy Machine Learning (SaTML) · doi:10.1109/satml64287.2025.00033 · Cited by 64
“By using SNARKs, we can keep the instantiation generic and universally prove its completeness and security for any triplet ( f I , f T , f U ) .”
InfluentialNew Negative Results on Differing-Inputs Obfuscation
Bellare, M., Stepanovs, I., & Waters, B. R. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-49896-5_28 · Cited by 47
“Also [37] build diO for TMs with unbounded inputs from public-coin diO for NC1, fully homomorphic encryption with decryption in NC1 and public-coin SNARKs.”
BackgroundBlockchain for V2X: Applications and Architectures
Meijers, J., Michalopoulos, P., Motepalli, S., Zhang, G., Zhang, S., Veneris, A. G., & Jacobsen, H. (2022) · IEEE Open Journal of Vehicular Technology · doi:10.1109/ojvt.2022.3172709 · Cited by 56
“Many of the designs that offer the strongest privacy protections are based on zero-knowledge succinct non-interactive arguments of knowledge (ZK-SNARK) [114], which are capable of near-perfect privacy protection.”
BackgroundVerifiable Computation on Outsourced Encrypted Data
Lai, J., Deng, R. H., Pang, H., & Weng, J. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11203-9_16 · Cited by 46
“We refer the reader to [15] for discussions on other related effort, such as succinct noninteractive arguments of knowledge [16].”
Refereed delegation of computation
Canetti, R., Riva, B., & Rothblum, G. N. (2013) · Information and Computation · doi:10.1016/j.ic.2013.03.003 · Cited by 58
Self-citationCocks–Pinch curves of embedding degrees five to eight and optimal ate pairing computation
Guillevic, A., Masson, S., & Thomé, E. (2020) · Designs Codes and Cryptography · doi:10.1007/s10623-020-00727-w · Cited by 45
“zero-knowledge proofs [11] used in the Zcash cryptocurrency and electronic voting.”
Zilch: A Framework for Deploying Transparent Zero-Knowledge Proofs
Mouris, D., & Tsoutsos, N. G. (2021) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2021.3074869 · Cited by 57
Quasi-Optimal SNARGs via Linear Multi-Prover Interactive Proofs
Boneh, D., Ishai, Y., Sahai, A., & Wu, D. J. (2018) · Lecture notes in computer science · doi:10.1007/978-3-319-78372-7_8 · Cited by 52
“Alternatively, one might ask whether a similar construction of quasi-optimal SNARGs is possible starting from standard PCPs or linear PCPs with quasioptimal prover complexity.”
BackgroundInfluentialOn Using zk-SNARKs and zk-STARKs in Blockchain-Based Identity Management
Drăgnoiu, A.-E., & Olimid, R. F. (2021) · Lecture notes in computer science · doi:10.1007/978-3-030-69255-1_9 · Cited by 49
Challenges in making blockchain privacy compliant for the digital world: some measures
Bansod, S., & Ragha, L. L. (2022) · Sadhana · doi:10.1007/s12046-022-01931-1 · Cited by 48
“2012 [29] Efficient secured, protocol Complex”
TRUESET: Faster verifiable set computations
Kosba, A. E., Papadopoulos, D., Papamanthou, C., Sayed, M. F., Shi, E., & Triandopoulos, N. (2014) · Cited by 53
Generalizing Homomorphic MACs for Arithmetic Circuits
Catalano, D., Fiore, D., Gennaro, R., & Nizzardo, L. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-54631-0_31 · Cited by 43
“Homomorphic signatures could be realized by using Succinct Non-interactive Arguments of Knowledge (SNARKs) [6].”
MethodA survey of elliptic curves for proof systems
Aranha, D. F., Housni, Y. E., & Guillevic, A. (2022) · Designs Codes and Cryptography · doi:10.1007/s10623-022-01135-y · Cited by 49
“Proofsystems were introduced in [70] and extensively studied both in theoretical and applied settings [7, 82, 94, 105].”
BackgroundPractical Non-Malleable Codes from l-more Extractable Hash Functions
Kiayias, A., Liu, F.-H., & Tselekounis, Y. (2016) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2976749.2978352 · Cited by 51
“It turns out that, in order to apply the methodology described above, a slightly stronger flavor of non-malleability is required for the underlying code, which we formalize as randomness simulatable non-malleable codes .”
BackgroundMethodInfluentialPractical Aggregate Signature from General Elliptic Curves, and Applications to Blockchain
Zhao, Y. (2019) · ACM Asia Conference on Computer and Communications Security (ASIA CCS) · doi:10.1145/3321705.3329826 · Cited by 42
Fatz, F., Hake, P., & Fettke, P. (2019) · IEEE Conference on Business Informatics · doi:10.1109/cbi.2019.00071 · Cited by 41
“However, the recently discussed succinct non-interactive arguments of knowledge (zk-SNARK) [27] seem to be applicable to the described blockchain dilemma.”
BackgroundTwo Protocols for Delegation of Computation
Canetti, R., Riva, B., & Rothblum, G. N. (2012) · Lecture notes in computer science · doi:10.1007/978-3-642-32284-6_3 · Cited by 44
“Further extensions of this construction give a two-message protocol in the plain model, with similar complexity advantages [CL08,BCCR12,GLR11,DFH12].”
MethodSelf-citationAnanth, P., Chandran, N., Goyal, V., Kanukurthi, B., & Ostrovsky, R. (2014) · Lecture notes in computer science · doi:10.1007/978-3-642-54631-0_9 · Cited by 43
Constant-Round Interactive Proofs for Delegating Computation
Reingold, O., Rothblum, G. N., & Rothblum, R. D. (2019) · SIAM Journal on Computing · doi:10.1137/16m1096773 · Cited by 50
Quadratic Span Programs and Succinct NIZKs without PCPs.Preprint
Gennaro, R., Gentry, C., Parno, B. J., & Raykova, M. (2012) · IACR Cryptology ePrint Archive · Cited by 51
Xu, S., Cai, X., Zhao, Y., Ren, Z., Du, L., Wang, Q., & Zhou, J. (2021) · Future Generation Computer Systems · doi:10.1016/j.future.2021.09.034 · Cited by 41
Towards Practical Auditing of Dynamic Data in Decentralized Storage
Duan, H., Du, Y., Zheng, L., Wang, C., Au, M. H., & Wang, Q. (2022) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2022.3142611 · Cited by 36
“In particular, it uses zkSnark [11] to create succinct and easy-to-verify proofs.”
MethodConstant-Round Concurrent Zero Knowledge from P-Certificates
Chung, K.-M., Lin, H., & Pass, R. (2013) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2013.14 · Cited by 41
Azar, P. D., & Micali, S. M. (2012) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/2213977.2214069 · Cited by 40
“General interactive proofs are not practical and there has been plenty of work in reducing the number of messages exchanged as well as the amount of work that the verifier needs to do [35, 33, 31, 25, 13, 7, 36, 9, 22, 15, 16, 2, 10, 38, 17].”
BackgroundFast Reductions from RAMs to Delegatable Succinct Constraint Satisfaction Problems.Preprint
Ben‐Sasson, E., Chiesa, A., Genkin, D., & Tromer, E. (2012) · IACR Cryptology ePrint Archive · Cited by 35
Self-citationFunctional Signatures and Pseudorandom Functions
Boyle, E., Goldwasser, S., & Ivan, I. (2013) · Cited by 33
Delegating Computations with (Almost) Minimal Time and Space Overhead
Holmgren, J., & Rothblum, R. D. (2018) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2018.00021 · Cited by 39
“[29], [42], [43], [44], [45]) implementing, optimizing and improving the [25] protocol.”
Families of SNARK-Friendly 2-Chains of Elliptic Curves
Housni, Y. E., & Guillevic, A. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-07085-3_13 · Cited by 32
“A SNARK [33,35,7] is a cryptographic primitive that enables a prover to prove to a verifier the knowledge of a satisfying witness to a non-deterministic (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.”
Privacy-Preserving Energy Trading Using Blockchain and Zero Knowledge Proof
Hou, D., Zhang, J., Huang, S., Peng, Z., Ma, J., & Zhu, X. (2022) · IEEE International Conference on Blockchain (Blockchain) · doi:10.1109/blockchain55522.2022.00064 · Cited by 37
“In this framework, a non-interactive Zero-knowledge proof method called Zero-Knowledge Succinct Non-Interactive Ar-gument of Knowledge (zkSNARKs) [10] is employed.”
MethodAn Expressive (Zero-Knowledge) Set Accumulator
Zhang, Y., Katz, J. I., & Papamanthou, C. (2017) · IEEE European Symposium on Security and Privacy · doi:10.1109/eurosp.2017.35 · Cited by 41
“General-purpose verifiable computation [23], [9], [10], [24], [11] and implementations thereof [40], [39], [4], [16], [42], [6], [5], [20] can provide expressive zero-knowledge set accumulators.”
FuturesMEX: Secure, Distributed Futures Market Exchange
Massacci, F., Ngo, C. N., Nie, J., Venturi, D., & Williams, J. M. (2018) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2018.00028 · Cited by 41
“Later work (starting with [22], [13]), showed that zk-SNARKs exist in the standard model, based on so-called knowledge-of-exponent assumptions; interestingly, these type of assumptions seem to be inherent for constructing zk-SNARKs [27].”
BackgroundAlgebraic Reductions of Knowledge
Kothapalli, A., & Parno, B. J. (2023) · Lecture notes in computer science · doi:10.1007/978-3-031-38551-3_21 · Cited by 34
“…be composed, this opens up the ability to modularly reason about knowledge-assumption-based succinct non-interactive arguments of knowledge (SNARKs [BCCT12,GW11]) and incrementally verifiable computation [Val08], which currently fall back on composing extractors in intricate ways [KMP20, KST22,BCL…”
BackgroundWI Is Not Enough: Zero-Knowledge Contingent (Service) Payments Revisited
Fuchsbauer, G. (2019) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3319535.3354234 · Cited by 39
“Soundness of all zkSNARK systems from the literature relies on strong cryptographic assumptions (so-called knowledge assumptions), for which there is evidence that they might be unavoidable [GW11, BCCT12].”
BackgroundLiu, Z., & Tromer, E. (2022) · Lecture notes in computer science · doi:10.1007/978-3-031-15802-5_26 · Cited by 41
“Alternatively the latter assumption can be replaced by a zk-SNARK proof [10], appended to the ciphertext, of the statement “( (cid:126)a,b ) was constructed as a linear combination of public-key vectors”.”
Self-citationVerifiable Computing Applications in Blockchain
Šimunić, S., Bernaca, D., & Lenac, K. (2021) · IEEE Access · doi:10.1109/access.2021.3129314 · Cited by 41
“One of the NIZKP is zk-SNARK [3], [36]–[38], which stands for "Zero-Knowledge Succinct Non-Interactive Argument of Knowledge".”
BackgroundMethodSuccinct Zero-Knowledge Batch Proofs for Set Accumulators
Campanelli, M., Fiore, D., Han, S., Kim, J., Kolonelos, D., & Oh, H. (2022) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3548606.3560677 · Cited by 40
“Both these problems can be solved via the use of zkSNARKs [13, 47], cryptographic proof systems that enable a prover to convince a verifier about the veracity of statements of the form “given a function F and a public input x , there is a secret w such that F (x,w) is true”.”
BackgroundAdaptively-Sound Succinct Arguments for NP from Indistinguishability Obfuscation
Waters, B. R., & Wu, D. J. (2024) · ACM Symposium on Theory of Computing (STOC) · doi:10.1145/3618260.3649671 · Cited by 30
Kalai, Y. T., & Rothblum, R. D. (2015) · Lecture notes in computer science · doi:10.1007/978-3-662-48000-7_21 · Cited by 30
On the (In)Security of SNARKs in the Presence of Oracles
Fiore, D., & Nitulescu, A. (2016) · Lecture notes in computer science · doi:10.1007/978-3-662-53641-4_5 · Cited by 37
Accelerating Zero-Knowledge Proofs Through Hardware-Algorithm Co-Design
Samardzic, N., Langowski, S., Devadas, S., & Sánchez, D. (2024) · IEEE/ACM International Symposium on Microarchitecture (MICRO) · doi:10.1109/micro61859.2024.00035 · Cited by 45
“2 The most studied and widely used of ZKPs are zk-SNARKs [17] (zero-knowledge, succinct, non-interactive arguments of knowledge), because they have attractive properties: (1) zero-knowledge means the verifier does not learn anything about the private witness ¯ w ; (2) succinctness means that proof…”
Homomorphic Signatures and Message Authentication Codes
Catalano, D. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-10879-7_29 · Cited by 29
Adaptively Secure Fully Homomorphic Signatures Based on Lattices.
Boyen, X., Fan, X., & Shi, E. (2014) · Cited by 29
An Efficient Self-blindable Attribute-Based Credential Scheme
Ringers, S., Verheul, E. R., & Hoepman, J.-H. (2017) · Lecture notes in computer science · doi:10.1007/978-3-319-70972-7_1 · Cited by 29
“Additionally, we have found that the whLRSW assumption can be proven by taking an extension [11] of the Known Exponent Assumption [22], so that unforgeability of our scheme can also be proven by using this assumption.”
True2F: Backdoor-Resistant Authentication Tokens
Dauterman, E., Corrigan-Gibbs, H., Mazières, D., Boneh, D., & Rizzo, D. (2019) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp.2019.00048 · Cited by 30
“Cryptographic techniques, such as verifiable computation protocols, can audit a chip’s behavior [8, 14, 19, 62, 66, 77, 101, 116, 118].”
BackgroundVerifying computations without reexecuting them: from theoretical possibility to near-practicality.Preprint
Walfish, M., & Blumberg, A. J. (2013) · Electronic colloquium on computational complexity · Cited by 31
Succinct Non-Interactive Arguments via Linear Interactive Proofs
Bitansky, N., Chiesa, A., Ishai, Y., Ostrovsky, R., & Paneth, O. (2022) · Journal of Cryptology · doi:10.1007/s00145-022-09424-4 · Cited by 31
“constructing a zero-knowledge SNARK via the result of [11] and then invoke the result of [12], one must be mindful to rely on (not-necessarily-succinct) non-interactive arguments of knowledge where the extractor does not require a trapdoor.”
BackgroundMethodInfluentialSelf-citationFully Homomorphic Encryption Beyond IND-CCA1 Security: Integrity Through Verifiability
Manulis, M., & Nguyen, J. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-58723-8_3 · Cited by 27
“We use a SNARK [12] to do the ”linking” we require for IND-vCCA as mentioned above.”
MethodThreshold Signatures in the Multiverse
Baird, L. C., Garg, S., Jain, A., Mukherjee, P., Sinha, R., Wang, M., & Zhang, Y. (2023) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46215.2023.10179436 · Cited by 27
“To avoid such scaling issues, one can devise an alternative solution by using succinct non-interactive arguments of knowledge (SNARK) [11], [12].”
BackgroundMethodALITHEIA: Towards Practical Verifiable Graph Processing
Zhang, Y., Papamanthou, C., & Katz, J. I. (2014) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2660267.2660354 · Cited by 31
“A VC protocol for graph algorithms can be derived in theory via black-box use of existing general-purpose VC schemes [18, 14, 24, 9, 10, 19, 11], or one of the systems that have been built to apply these techniques [33, 32, 30, 7, 12, 36].”
BackgroundMethodDecentralized Identity Authentication with Auditability and Privacy
Alangot, B., Szałachowski, P., Dinh, T. T. A., Meftah, S., Gana, J. I., Aung, K. M. M., & Li, Z. (2022) · Algorithms · doi:10.3390/a16010004 · Cited by 26
“In practice, VRFs can be implemented with unique signatures. zk-SNARK . zk-SNARK (Zero-Knowledge Succinct Non-Interactive Argument of Knowledge) [19] is a non-interactive zero-knowledge proving system that allows one to prove and verify the integrity of an arbitrary computation (represented as an…”
Zerocash: Decentralized Anonymous Payments from Bitcoin (extended version)
Ben‐Sasson, E., Chiesa, A., Garman, C., Green, M., Miers, I., Tromer, E., & Virza, M. (2014) · Cited by 27
Self-citationHardcaml MSM: A High-Performance Split CPU-FPGA Multi-Scalar Multiplication Engine
Ray, A., Devlin, B., Quah, F. Y., & Yesantharao, R. (2024) · ACM/SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA) · doi:10.1145/3626202.3637577 · Cited by 30
Succinct Malleable NIZKs and an Application to Compact Shuffles
Chase, M., Kohlweiss, M., Lysyanskaya, A., & Meiklejohn, S. (2013) · Lecture notes in computer science · doi:10.1007/978-3-642-36594-2_6 · Cited by 30
“[3, 4], care must be taken with this kind of recursive composition of SNARGs, as the size of the extractor can quickly blow up as we continue to extract proofs from other proofs; we can therefore construct t-tiered malleable SNARGs (i.”
BackgroundMethodCompact Certificates of Collective Knowledge
Micali, S. M., Reyzin, L., Vlachos, G., Wahby, R. S., & Zeldovich, N. (2021) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp40001.2021.00096 · Cited by 30
“Several lines of work on succinct non-interactive arguments of knowledge (SNARKs) [3, 8, 9, 11, 12, 16, 17, 24, 34–36, 47–49, 58, 73, 83, 90, 91] allow a prover to construct a short proof for any NP statement.”
BackgroundZapper: Smart Contracts with Data and Identity Privacy
Steffen, S., Bichsel, B., & Vechev, M. (2022) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/3548606.3560622 · Cited by 30
“Zero-knowledge succinct non-interactive arguments of knowledge (zk-SNARKs) [11, 29] are NIZK proof constructions allowing efficient proof generation and verification for any arithmetic proof circuit φ.”
BackgroundAdaptive Security in SNARGs via iO and Lossy Functions
Waters, B. R., & Zhandry, M. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-68403-6_3 · Cited by 24
Practical Homomorphic Message Authenticators for Arithmetic Circuits
Catalano, D., & Fiore, D. (2017) · Journal of Cryptology · doi:10.1007/s00145-016-9249-1 · Cited by 24
Indistinguishability Obfuscation for RAM Programs and Succinct Randomized Encodings
Bitansky, N., Canetti, R., Garg, S., Holmgren, J., Jain, A., Lin, H., Pass, R., Telang, S., & Vaikuntanathan, V. (2018) · SIAM Journal on Computing · doi:10.1137/15m1050963 · Cited by 25
Self-citationA Zero-Knowledge Version of vSQL.Preprint
Zhang, Y., Genkin, D., Katz, J. I., Papadopoulos, D., & Papamanthou, C. (2017) · IACR Cryptology ePrint Archive · Cited by 65
Multi-Server Verifiable Computation of Low-Degree Polynomials
Zhang, L. F., & Wang, H. (2022) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp46214.2022.9833792 · Cited by 25
Quan, Y. (2022) · IEEE Access · doi:10.1109/access.2022.3227394 · Cited by 23
“For example, Bao et al proposed Lockmix, a secure mix service for Bitcoin [9], and in 2012, Bitansky et al proposed zero-knowledge Succinct Non-interactive Argument of Knowledge (SNARK) [10].”
BackgroundHow to Use SNARKs in Universally Composable Protocols.Preprint
Kosba, A. E., Zhao, Z., Miller, A. E., Qian, Y., Chan, T.-H. H., Papamanthou, C., Pass, R., Shelat, A. A., & Shi, E. (2015) · IACR Cryptology ePrint Archive · Cited by 30
On the Existence of Extractable One-Way Functions
Bitansky, N., Canetti, R., Paneth, O., & Rosen, A. (2016) · SIAM Journal on Computing · doi:10.1137/140975048 · Cited by 24
Self-citationBlockchain vs GDPR in Collaborative Data Governance
Dutta, R., Das, A., Dey, A., & Bhattacharya, S. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-60816-3_10 · Cited by 22
Indistinguishability Obfuscation vs. Auxiliary-Input Extractable Functions: One Must Fall.
Bitansky, N., Canetti, R., Paneth, O., & Rosen, A. (2013) · Cited by 21
Self-citationAdaptively Sound Zero-Knowledge SNARKs for UP
Mathialagan, S., Peters, S., & Vaikuntanathan, V. (2024) · Lecture notes in computer science · doi:10.1007/978-3-031-68403-6_2 · Cited by 22
On Succinct Arguments and Witness Encryption from Groups
Barta, O., Ishai, Y., Ostrovsky, R., & Wu, D. J. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-56784-2_26 · Cited by 23
Integrity Authentication for SQL Query Evaluation on Outsourced Databases: A Survey
Zhang, B., Dong, B., & Wang, H. (2019) · IEEE Transactions on Knowledge and Data Engineering · doi:10.1109/tkde.2019.2947061 · Cited by 23
“generic verification approaches [53], [54].”
An Introduction to Zero-Knowledge Proofs in Blockchains and Economics
Berentsen, A., Lenzi, J., & Nyffenegger, R. (2023) · doi:10.20955/r.105.280-94 · Cited by 20
Enhancing Privacy and Integrity in Computing Services Provisioning Using Blockchain and Zk-SNARKs
Ballesteros-Rodríguez, A., Sánchez‐Alonso, S., & Sicilia, M. (2024) · IEEE Access · doi:10.1109/access.2024.3447785 · Cited by 22
“[24] came up with zk-SNARKs from the protocol described by [25].”
MethodSPARKs: Succinct Parallelizable Arguments of Knowledge
Ephraim, N., Freitag, C., Komargodski, I., & Pass, R. (2020) · Lecture notes in computer science · doi:10.1007/978-3-030-45721-1_25 · Cited by 24
“Bitansky et al. [12] (following Valiant’s [41] incrementally verifiable computation framework using recursive proof composition) construct complexity-preserving SNARKs, in which both the time and space of the underlying computation up to (multiplicative) polynomial factors in the security parameter.”
BackgroundMethodVerifiable Delegation of Computations with Storage-Verification Trade-off
Zhang, L. F., & Safavi–Naini, R. (2014) · Lecture notes in computer science · doi:10.1007/978-3-319-11203-9_7 · Cited by 20
“The SNARGs or SNARKs [3,9], gives a non-interactive scheme for delegating computation.”
BackgroundAttribute-based Key Exchange with General Policies
Kolesnikov, V., Krawczyk, H., Lindell, Y., Malozemoff, A. J., & Rabin, T. (2016) · ACM SIGSAC Conference on Computer and Communications Security (CCS) · doi:10.1145/2976749.2978359 · Cited by 20
“(t-KEA [11, 10]) Let G be a cyclic group of prime order q.”
BackgroundMethodPrivacy-Preserving Analytics for Data Markets Using MPC
Koch, K., Krenn, S., Pellegrino, D., & Ramacher, S. (2021) · IFIP advances in information and communication technology · doi:10.1007/978-3-030-72465-8_13 · Cited by 28
ABE Squared: Accurately Benchmarking Efficiency of Attribute-Based Encryption
de la Piedra, A., Venema, M., & Alpár, G. (2022) · IACR Transactions on Cryptographic Hardware and Embedded Systems · doi:10.46586/tches.v2022.i2.192-239 · Cited by 19
A Secure Sidechain for Decentralized Trading in Internet of Things
Gai, F., Niu, J., Jalalzai, M. M., Tabatabaee, S. A., & Feng, C. (2023) · IEEE Internet of Things Journal · doi:10.1109/jiot.2023.3300051 · Cited by 21
“Recent advances in zero-knowledge proof (ZKP) technologies [30], [31] are introduced to regulate the operator, e.g., NOCUST-ZKP [28] and ZK-rollup (ZKR) [29].”
BackgroundEfficient verifiable databases with additional insertion and deletion operations in cloud computing
Wang, Q., Zhou, F., Xu, J. F., & Xu, Z. (2020) · Future Generation Computer Systems · doi:10.1016/j.future.2020.09.028 · Cited by 19
VerITAS: Verifying Image Transformations at Scale
Datta, T., Chen, B., & Boneh, D. (2025) · IEEE Symposium on Security and Privacy (S&P) · doi:10.1109/sp61157.2025.00097 · Cited by 30
“In this paper, we present VerITAS (Verifying Image Transformations At Scale), a system that uses succinct zero-knowledge arguments (zk-SNARKs) [11] to prove the provenance of edited photos.”
Ateniese, G., Dagdelen, Ö., Damgård, I., & Venturi, D. (2016) · Future Generation Computer Systems · doi:10.1016/j.future.2016.01.008 · Cited by 21
“The standard definition of all-or-nothing transform requires that it should be hard to reconstruct a message if not all the bits of its encoding are known.”
BackgroundHow to Delegate Computations: The Power of No-Signaling Proofs
Kalai, Y. T., Raz, R., & Rothblum, R. D. (2021) · Journal of the ACM · doi:10.1145/3456867 · Cited by 18
FileBounty: Fair Data Exchange
Janin, S., Qin, K., Mamageishvili, A., & Gervais, A. (2020) · IEEE European Symposium on Security and Privacy Workshops (EuroS&PW) · doi:10.1109/eurospw51379.2020.00056 · Cited by 18
Enabling Generic Verifiable Aggregate Query on Blockchain Systems
Zhu, Y., Zhang, Z., Jin, C., & Zhou, A. (2020) · IEEE International Conference on Parallel and Distributed Systems (ICPADS) · doi:10.1109/icpads51040.2020.00066 · Cited by 18
“General approaches [11] [12] [13] have better expressiveness based on SNARKs [14], with efficient verification and constant size proof.”
BackgroundValidCNN: A Large-Scale CNN Predictive Integrity Verification Scheme Based on zk-SNARK
Fan, Y., Ma, K., Zhang, L., Lei, X., Xu, G., & Tan, G. (2024) · IEEE Transactions on Dependable and Secure Computing · doi:10.1109/tdsc.2024.3371643 · Cited by 24
“Furthermore,numerousotherscholars haveimplementedpredictiveintegrityverificationforCNNs based on zk-SNARKs [21], [22], [23], [24], [25].”
Private Outsourcing of Polynomial Evaluation and Matrix Multiplication Using Multilinear Maps
Zhang, L. F., & Safavi–Naini, R. (2013) · Lecture notes in computer science · doi:10.1007/978-3-319-02937-5_18 · Cited by 17
“In the context of VC, the non-interactive proofs or arguments are much more desirable and have been considered in [22, 4] for various computations.”
BackgroundInfluential
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.