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
Non-interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers
Gennaro, R., Gentry, C., & Parno, B. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_25 · Cited by 1,145
Minimum disclosure proofs of knowledge
Brassard, G., Chaum, D., & Crépeau, C. (1988) · Journal of Computer and System Sciences · doi:10.1016/0022-0000(88)90005-0 · Cited by 959
Worst‐Case to Average‐Case Reductions Based on Gaussian Measures
Micciancio, D., & Regev, O. (2007) · SIAM Journal on Computing · doi:10.1137/s0097539705447360 · Cited by 907
Shamir, A. (1992) · Journal of the ACM · doi:10.1145/146585.146609 · Cited by 662 · cited 3×
“IP = PSPACE.”
BackgroundInfluentialDefinitions and properties of zero-knowledge proof systems
Goldreich, O., & Oren, Y. (1994) · Journal of Cryptology · doi:10.1007/bf00195207 · Cited by 614
Generating Hard Instances of Lattice ProblemsPreprint
Ajtai, M. (1996) · Electronic colloquium on computational complexity · Cited by 606
A note on efficient zero-knowledge proofs and arguments (extended abstract)
Kilian, J. (1992) · Proceedings of the twenty-fourth annual ACM symposium on Theory of computing - STOC '92 · doi:10.1145/129712.129782 · Cited by 606
Computationally Private Information Retrieval with Polylogarithmic Communication
Cachin, C., Micali, S., & Stadler, M. (1999) · Lecture Notes in Computer Science · doi:10.1007/3-540-48910-x_28 · Cited by 579
Leakage-Resilient Cryptography
Dziembowski, S., & Pietrzak, K. (2008) · 2008 49th Annual IEEE Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.56 · Cited by 504
Delegating computation: interactive proofs for muggles
Goldwasser, S., Kalai, Y. T., & Rothblum, G. N. (2008) · Proceedings of the fortieth annual ACM symposium on Theory of computing · doi:10.1145/1374376.1374396 · Cited by 484
Razborov, A. A., & Rudich, S. (1997) · Journal of Computer and System Sciences · doi:10.1006/jcss.1997.1494 · Cited by 479
Separating succinct non-interactive arguments from all falsifiable assumptions
Gentry, C., & Wichs, D. (2011) · Proceedings of the forty-third annual ACM symposium on Theory of computing · doi:10.1145/1993636.1993651 · Cited by 456
Short Pairing-Based Non-interactive Zero-Knowledge Arguments
Groth, J. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-17373-8_19 · Cited by 440
Micali, S. (2000) · SIAM Journal on Computing · doi:10.1137/s0097539795284959 · Cited by 424
Gama, N., & Nguyen, P. Q. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78967-3_3 · Cited by 413 · cited 1×
“, [33] conjecture, from experimental evidence, that 1.”
Improved Delegation of Computation Using Fully Homomorphic Encryption
Chung, K.-M., Kalai, Y., & Vadhan, S. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14623-7_26 · Cited by 403
Verifiable Delegation of Computation over Large Datasets
Benabbas, S., Gennaro, R., & Vahlis, Y. (2011) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-22792-9_7 · Cited by 379
Does co-NP have short interactive proofs?
Boppana, R. B., Hastad, J., & Zachos, S. (1987) · Information Processing Letters · doi:10.1016/0020-0190(87)90232-8 · Cited by 363
On Cryptographic Assumptions and Challenges
Naor, M. (2003) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-45146-4_6 · Cited by 360
Towards Practical Public Key Systems Secure Against Chosen Ciphertext attacks
Damgård, I. (2007) · Lecture Notes in Computer Science · doi:10.1007/3-540-46766-1_36 · Cited by 357
Single-Database Private Information Retrieval with Constant Communication Rate
Gentry, C., & Ramzan, Z. (2005) · Lecture Notes in Computer Science · doi:10.1007/11523468_65 · Cited by 313
New lattice-based cryptographic constructions
Regev, O. (2004) · Journal of the ACM · doi:10.1145/1039488.1039490 · Cited by 292
Blum, M. (1981) · International Cryptology Conference · Cited by 256
Universal arguments and their applications
Barak, B., & Goldreich, O. (2003) · Proceedings 17th IEEE Annual Conference on Computational Complexity · doi:10.1109/ccc.2002.1004355 · Cited by 244
The Knowledge-of-Exponent Assumptions and 3-Round Zero-Knowledge Protocols
Bellare, M., & Palacio, A. (2004) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-28628-8_17 · Cited by 235
Complexity of a determinate algorithm for the discrete logarithm
Nechaev, V. I. (1994) · Mathematical Notes · doi:10.1007/bf02113297 · Cited by 232
From Secrecy to Soundness: Efficient Verification via Secure Computation: (Extended Abstract)
Applebaum, B., Ishai, Y., & Kushilevitz, E. (2010) · Lecture Notes in Computer Science · doi:10.1007/978-3-642-14165-2_14 · Cited by 198
On Bounded Distance Decoding, Unique Shortest Vectors, and the Minimum Distance Problem
Lyubashevsky, V., & Micciancio, D. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03356-8_34 · Cited by 192
On the existence of 3-round zero-knowledge protocols
Hada, S., & Tanaka, T. (1998) · Lecture Notes in Computer Science · doi:10.1007/bfb0055744 · Cited by 175
Incrementally Verifiable Computation or Proofs of Knowledge Imply Time/Space Efficiency
Valiant, P. (2008) · Lecture Notes in Computer Science · doi:10.1007/978-3-540-78524-8_1 · Cited by 175
Linear zero-knowledge---a note on efficient zero-knowledge proofs and arguments
Cramer, R., & Damgård, I. (1997) · Proceedings of the twenty-ninth annual ACM symposium on Theory of computing - STOC '97 · doi:10.1145/258533.258635 · Cited by 170
Communication preserving protocols for secure function evaluation
Naor, M., & Nissim, K. (2001) · Proceedings of the thirty-third annual ACM symposium on Theory of computing · doi:10.1145/380752.380855 · Cited by 165
Key distribution system based on identification information
Okamoto, E., & Tanaka, K. (1989) · IEEE Journal on Selected Areas in Communications · doi:10.1109/49.17711 · Cited by 159
Short PCPs with Polylog Query Complexity
Ben-Sasson, E., & Sudan, M. (2008) · SIAM Journal on Computing · doi:10.1137/050646445 · Cited by 147
Optimal Verification of Operations on Dynamic Sets
Papamanthou, C., Tamassia, R., & Triandopoulos, N. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22792-9_6 · Cited by 144
Efficient Non-interactive Secure Computation
Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., & Sahai, A. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-20465-4_23 · Cited by 133
Secure 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
Chung, K.-M., Kalai, Y. T., Liu, F.-H., & Raz, R. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22792-9_9 · Cited by 131
Short PCPs Verifiable in Polylogarithmic Time
Ben‐Sasson, E., Goldreich, O., Harsha, P., Sudan, M., & Vadhan, S. (2005) · IEEE Conference on Computational Complexity (CCC) · doi:10.1109/ccc.2005.27 · Cited by 128
Proof-Carrying Data and Hearsay Arguments from Signature Cards.
Chiesa, A., & Tromer, E. (2010) · International Conference on Supercomputing · Cited by 123
Self-citationPerfect NIZK with Adaptive Soundness
Abe, M., & Fehr, S. (2007) · Springer eBooks · doi:10.1007/978-3-540-70936-7_7 · Cited by 118
Dense Subsets of Pseudorandom Sets
Reingold, O., Trevisan, L., Tulsiani, M., & Vadhan, S. (2008) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2008.38 · Cited by 106
Salvaging Merkle-Damgård for Practical Applications
Dodis, Y., Ristenpart, T., & Shrimpton, T. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-01001-9_22 · Cited by 104
On interactive proofs with a laconic prover
Goldreich, O., Vadhan, S., & Wigderson, A. (2002) · Computational Complexity · doi:10.1007/s00037-002-0169-0 · Cited by 97
Collision-Free Hashing from Lattice Problems
Goldreich, O., Goldwasser, S., & Halevi, S. (1996) · Cited by 92
On the complexity of interactive proofs with bounded communication
Goldreich, O., & Håstad, J. (1998) · Information Processing Letters · doi:10.1016/s0020-0190(98)00116-1 · Cited by 91
Delegation of Computation without Rejection Problem from Designated Verifier CS-Proofs.Preprint
Goldwasser, S., Lin, H., & Rubinstein, A. (2011) · IACR Cryptology ePrint Archive · Cited by 89
New lattice based cryptographic constructions
Regev, O. (2003) · Proceedings of the thirty-fifth annual ACM symposium on Theory of computing · doi:10.1145/780542.780603 · Cited by 84
Verifying computations with streaming interactive proofs
Cormode, G., Thaler, J., & Yi, K. (2011) · Proceedings of the VLDB Endowment · doi:10.14778/2047485.2047488 · Cited by 82
Targeted malleability: homomorphic encryption for restricted computations
Boneh, D., Segev, G., & Waters, B. R. (2012) · Conference on Innovations in Theoretical Computer Science · doi:10.1145/2090236.2090264 · Cited by 75
Aiello, W. A., Bhatt, S. N., Ostrovsky, R., & Rajagopalan, S. (2000) · Lecture notes in computer science · doi:10.1007/3-540-45022-x_39 · Cited by 70
Probabilistically Checkable Arguments
Kalai, Y. T., & Raz, R. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-03356-8_9 · Cited by 64
Succinct NP Proofs from an Extractability Assumption
Crescenzo, G. D., & Lipmaa, H. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-69407-6_21 · Cited by 61
Extractable Perfectly One-Way Functions
Canetti, R., & Dakdouk, R. R. (2008) · Lecture notes in computer science · doi:10.1007/978-3-540-70583-3_37 · Cited by 55
Self-citationCollision-Free Hashing from Lattice Problems
Goldreich, O., Goldwasser, S., & Halevi, S. (2011) · Lecture notes in computer science · doi:10.1007/978-3-642-22670-0_5 · Cited by 54
Okamoto-Tanaka Revisited: Fully Authenticated Diffie-Hellman with Minimal Overhead
Gennaro, R., Krawczyk, H., & Rabin, T. (2010) · Lecture notes in computer science · doi:10.1007/978-3-642-13708-2_19 · Cited by 46
Hidden Pairings and Trapdoor DDH Groups
Dent, A. W., & Galbraith⋆, S. D. (2006) · Lecture notes in computer science · doi:10.1007/11792086_31 · Cited by 45
On Round-Efficient Argument Systems
Wee, H. (2005) · Lecture notes in computer science · doi:10.1007/11523468_12 · Cited by 41
The Hardness of the DHK Problem in the Generic Group Model.Preprint
Dent, A. W. (2006) · IACR Cryptology ePrint Archive · Cited by 41
Towards a Theory of Extractable Functions
Canetti, R., & Dakdouk, R. R. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00457-5_35 · Cited by 40
Self-citationPrabhakaran, M., & Xue, R. (2009) · Lecture notes in computer science · doi:10.1007/978-3-642-00862-7_7 · Cited by 35
Two 1-Round Protocols for Delegation of Computation.Preprint
Canetti, R., Riva, B., & Rothblum, G. N. (2011) · IACR Cryptology ePrint Archive · Cited by 34
Self-citationPolylogarithmic two-round argument systems
Mie, T. (2008) · Journal of Mathematical Cryptology · doi:10.1515/jmc.2008.016 · Cited by 32
Succinct Non-Interactive Zero-Knowledge Proofs with Preprocessing for LOGSNP
Kalai, Y. T., & Raz, R. (2006) · Annual Symposium on Foundations of Computer Science · doi:10.1109/focs.2006.74 · Cited by 31
Efficient Pseudorandom Generators from Exponentially Hard One-Way Functions
Haitner, I., Harnik, D., & Reingold, O. (2006) · Lecture notes in computer science · doi:10.1007/11787006_20 · Cited by 22
Leaky Pseudo-Entropy Functions
Braverman, M., Hassidim, A., & Kalai, Y. T. (2011) · Cited by 16
Verifying Computations with Streaming Interactive ProofsPreprint
Cormode, G., Thaler, J., & Yi, K. (2011) · arXiv (Cornell University) · doi:10.48550/arxiv.1109.6882 · Cited by 7
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].”
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.