{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:58:28Z","timestamp":1781078308808,"version":"3.54.1"},"reference-count":127,"publisher":"Springer Science and Business Media LLC","issue":"4","license":[{"start":{"date-parts":[[2016,10,3]],"date-time":"2016-10-03T00:00:00Z","timestamp":1475452800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2017,10]]},"DOI":"10.1007\/s00145-016-9241-9","type":"journal-article","created":{"date-parts":[[2016,10,3]],"date-time":"2016-10-03T18:51:12Z","timestamp":1475520672000},"page":"989-1066","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":100,"title":["The Hunting of the SNARK"],"prefix":"10.1007","volume":"30","author":[{"given":"Nir","family":"Bitansky","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ran","family":"Canetti","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Shafi","family":"Goldwasser","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huijia","family":"Lin","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Aviad","family":"Rubinstein","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Eran","family":"Tromer","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2016,10,3]]},"reference":[{"key":"9241_CR1","doi-asserted-by":"crossref","unstructured":"W. Aiello, S N. Bhatt, R. Ostrovsky, S. Rajagopalan, Fast verification of any remote procedure call: Short witness-indistinguishable one-round proofs for NP, in Proceedings of the 27th International Colloquium on Automata, Languages and Programming, 2000, pp. 463\u2013474.","DOI":"10.1007\/3-540-45022-X_39"},{"key":"9241_CR2","doi-asserted-by":"crossref","unstructured":"J. Alwen, Y. Dodis, D. Wichs. Survey: Leakage resilience and the bounded retrieval model, in Information Theoretic Security, 4th International Conference, ICITS 2009, Shizuoka, Japan, December 3\u20136, 2009. Revised Selected Papers, 2009, pp. 1\u201318.","DOI":"10.1007\/978-3-642-14496-7_1"},{"key":"9241_CR3","doi-asserted-by":"crossref","unstructured":"M. Abe, S. Fehr. Perfect NIZK with adaptive soundness, in Proceedings of the 4th theory of cryptography conference, 2007, pp. 118\u2013136.","DOI":"10.1007\/978-3-540-70936-7_7"},{"key":"9241_CR4","doi-asserted-by":"crossref","unstructured":"B. Applebaum, Y. Ishai, E. Kushilevitz. From secrecy to soundness: efficient verification via secure computation, in Proceedings of the 37th international colloquium on automata, languages, and programming, 2010, pp. 152\u2013163.","DOI":"10.1007\/978-3-642-14165-2_14"},{"key":"9241_CR5","doi-asserted-by":"crossref","unstructured":"M. Ajtai. Generating hard instances of lattice problems, in Proceedings of the 28th annual ACM symposium on the theory of computing, 1996, pp. 99\u2013108.","DOI":"10.1145\/237814.237838"},{"key":"9241_CR6","unstructured":"S. Arora, C. Lund, R. Motwani, M. Sudan, M. Szegedy, Proof verification and the hardness of approximation problems, J. ACM, 45(3), (1998) pp. 501\u2013555."},{"key":"9241_CR7","unstructured":"S. Arora, S. Safra, Probabilistic checking of proofs: a new characterization of NP. J. ACM, 45(1), (1998) pp. 70\u2013122"},{"key":"9241_CR8","doi-asserted-by":"crossref","unstructured":"M. Backes, M. Barbosa, D. Fiore, R.M. Reischuk. ADSNARK: nearly practical and privacy-preserving proofs on authenticated data, in Proceedings of the 36th IEEE Symposium on Security and Privacy, S&P \u201915, 2015, pp. 271\u2013286.","DOI":"10.1109\/SP.2015.24"},{"key":"9241_CR9","doi-asserted-by":"crossref","unstructured":"N. Bitansky, A. Chiesa. Succinct arguments from multi-prover interactive proofs and their efficiency benefits, in Proceedings of the 32nd annual international cryptology conference, CRYPTO\u00a0\u201912, 2012, pp. 255\u2013272.","DOI":"10.1007\/978-3-642-32009-5_16"},{"issue":"2","key":"9241_CR10","doi-asserted-by":"publisher","first-page":"156","DOI":"10.1016\/0022-0000(88)90005-0","volume":"37","author":"G Brassard","year":"1988","unstructured":"Gilles Brassard, David Chaum, and Claude Cr\u00e9peau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156\u2013189, 1988.","journal-title":"Journal of Computer and System Sciences"},{"key":"9241_CR11","doi-asserted-by":"crossref","unstructured":"N. Bitansky, R. Canetti, A. Chiesa, E. Tromer, From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. Cryptology ePrint Archive, Report 2011\/443, 2011. http:\/\/eprint.iacr.org\/ .","DOI":"10.1145\/2090236.2090263"},{"key":"9241_CR12","doi-asserted-by":"crossref","unstructured":"N. Bitansky, R. Canetti, A. Chiesa, E. Tromer. From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again, in Proceedings of the 3rd innovations in theoretical computer science conference, ITCS\u00a0\u201912, 2012, pp. 326\u2013349.","DOI":"10.1145\/2090236.2090263"},{"key":"9241_CR13","doi-asserted-by":"crossref","unstructured":"N. Bitansky, R. Canetti, A. Chiesa, E. Tromer, Recursive composition and bootstrapping for SNARKs and proof-carrying data, in Proceedings of the 45th ACM symposium on the theory of computing, STOC\u00a0\u201913, 2013, pp. 111\u2013120.","DOI":"10.1145\/2488608.2488623"},{"key":"9241_CR14","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer, M. Virza. SNARKs for C: verifying program executions succinctly and in zero knowledge, in Proceedings of the 33rd annual international cryptology conference, CRYPTO\u00a0\u201913, 2013, pp. 90\u2013108.","DOI":"10.1007\/978-3-642-40084-1_6"},{"key":"9241_CR15","doi-asserted-by":"crossref","unstructured":"N. Bitansky, A. Chiesa, Y. Ishai, R. Ostrovsky, O. Paneth, Succinct non-interactive arguments via linear interactive proofs, in Proceedings of the 10th theory of cryptography conference, TCC\u00a0\u201913, 2013, pp. 315\u2013333.","DOI":"10.1007\/978-3-642-36594-2_18"},{"key":"9241_CR16","doi-asserted-by":"crossref","unstructured":"N. Bitansky, R. Canetti, O. Paneth, A. Rosen, On the existence of extractable one-way functions, in STOC, 2014.","DOI":"10.1145\/2591796.2591859"},{"key":"9241_CR17","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, A. Chiesa, E. Tromer, M. Virza. Scalable zero knowledge via cycles of elliptic curves, in Proceedings of the 34th annual international cryptology conference, CRYPTO\u00a0\u201914, pp. 276\u2013294, 2014. Extended version at http:\/\/eprint.iacr.org\/2014\/595 .","DOI":"10.1007\/978-3-662-44381-1_16"},{"key":"9241_CR18","unstructured":"E. Ben-Sasson, A. Chiesa, E. Tromer, M. Virza, Succinct non-interactive zero knowledge for a von Neumann architecture, in Proceedings of the 23rd USENIX security symposium, security\u00a0\u201914, pp. 781\u2013796, 2014. Extended version at http:\/\/eprint.iacr.org\/2013\/879 ."},{"key":"9241_CR19","doi-asserted-by":"crossref","unstructured":"M. Blum, P. Feldman, S. Micali, Non-interactive zero-knowledge and its applications (extended abstract), in Proceedings of the 20th annual ACM symposium on theory of computing, May 2\u20134, 1988, Chicago, IL, USA, 1988, pp. 103\u2013112.","DOI":"10.1145\/62212.62222"},{"key":"9241_CR20","unstructured":"B. Barak, O. Goldreich. Universal arguments and their applications. SIAM J. Comput. 38(5), pp. 1661\u20131694, 2008. Preliminary version appeared in CCC\u00a0\u201902."},{"key":"9241_CR21","doi-asserted-by":"crossref","unstructured":"B. Barak, O. Goldreich, S. Goldwasser, Y. Lindell. Resettably-sound zero-knowledge and its applications, in FOCS, 2001, pp. 116\u2013125.","DOI":"10.1109\/SFCS.2001.959886"},{"key":"9241_CR22","doi-asserted-by":"crossref","unstructured":"B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.P. Vadhan, K.\u00a0Yang. On the (im)possibility of obfuscating programs, SIAM J. Comput., 59(2), 2012.","DOI":"10.1145\/2160158.2160159"},{"key":"9241_CR23","doi-asserted-by":"crossref","unstructured":"S. Benabbas, R. Gennaro, Y. Vahlis. Verifiable delegation of computation over large datasets, in Proceedings of the 31st annual international cryptology conference, 2011, pp. 111\u2013131.","DOI":"10.1007\/978-3-642-22792-9_7"},{"key":"9241_CR24","unstructured":"M. Braverman, A. Hassidim, Y.T. Kalai. Leaky pseudo-entropy functions. In Proceedings of the 2nd symposium on innovations in computer science, 2011, pp. 353\u2013366."},{"issue":"2","key":"9241_CR25","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"RB Boppana","year":"1987","unstructured":"Ravi\u00a0B. Boppana, Johan H\u00e5stad, and Stathis Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25(2):127\u2013132, 1987.","journal-title":"Inf Process Lett"},{"key":"9241_CR26","unstructured":"M. Blum. Coin flipping by telephone, in Proceedings of the 18th annual international cryptology conference, 1981, pp. 11\u201315."},{"key":"9241_CR27","doi-asserted-by":"crossref","unstructured":"M. Bellare, A. Palacio. The knowledge-of-exponent assumptions and 3-round zero-knowledge protocols, in Proceedings of the 24th annual international cryptology conference, 2004, pp. 273\u2013289.","DOI":"10.1007\/978-3-540-28628-8_17"},{"key":"9241_CR28","unstructured":"E. Boyle, R. Pass, Limits of extractability assumptions with distributional auxiliary input. Cryptology ePrint Archive, Report 2013\/703, 2013. http:\/\/eprint.iacr.org\/ ."},{"key":"9241_CR29","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, A. Chiesa, D. Genkin, E. Tromer. On the concrete efficiency of probabilistically-checkable proofs, in Proceedings of the 45th ACM symposium on the theory of computing, STOC\u00a0\u201913, 2013.","DOI":"10.1145\/2488608.2488681"},{"key":"9241_CR30","doi-asserted-by":"crossref","unstructured":"E. Ben-Sasson, O. Goldreich, P. Harsha, M. Sudan, S. Vadhan, Short PCPs verifiable in polylogarithmic time, in Proceedings of the 20th annual IEEE conference on computational complexity, 2005, pp. 120\u2013134.","DOI":"10.1109\/CCC.2005.27"},{"issue":"2","key":"9241_CR31","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/050646445","volume":"38","author":"E Ben-Sasson","year":"2008","unstructured":"Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM Journal on Computing, 38(2):551\u2013607, 2008.","journal-title":"SIAM J. Comput."},{"key":"9241_CR32","doi-asserted-by":"crossref","unstructured":"D. Boneh, G. Segev, B. Waters. Targeted malleability: Homomorphic encryption for restricted computations. Cryptology ePrint Archive, Report 2011\/311, 2011.","DOI":"10.1145\/2090236.2090264"},{"key":"9241_CR33","doi-asserted-by":"crossref","unstructured":"Z. Brakerski, V. Vaikuntanathan, Efficient fully homomorphic encryption from (standard) LWE, in Proceedings of the 51th annual IEEE symposium on foundations of computer science, 2011.","DOI":"10.1109\/FOCS.2011.12"},{"key":"9241_CR34","doi-asserted-by":"crossref","unstructured":"R. Canetti, Towards realizing random oracles: hash functions that hide all partial information, in Proceedings of the 17th annual international cryptology conference, 1997, pp. 455\u2013469.","DOI":"10.1007\/BFb0052255"},{"key":"9241_CR35","doi-asserted-by":"crossref","unstructured":"R. Canetti, Universally composable security: a new paradigm for cryptographic protocols, in Proceedings of the 42nd annual IEEE symposium on foundations of computer science, 2001, pp. 136\u2013145.","DOI":"10.1109\/SFCS.2001.959888"},{"key":"9241_CR36","doi-asserted-by":"crossref","unstructured":"R. Canetti, R.R. Dakdouk, Extractable perfectly one-way functions, in Proceedings of the 35th international colloquium on automata, languages and programming, 2008, pp. 449\u2013460.","DOI":"10.1007\/978-3-540-70583-3_37"},{"key":"9241_CR37","doi-asserted-by":"crossref","unstructured":"R. Canetti, R.R. Dakdouk, Towards a theory of extractable functions, in Proceedings of the 6th theory of cryptography conference, 2009, pp. 595\u2013613.","DOI":"10.1007\/978-3-642-00457-5_35"},{"key":"9241_CR38","doi-asserted-by":"crossref","unstructured":"C. Costello, C. Fournet, J. Howell, M. Kohlweiss, B. Kreuter, M. Naehrig, B. Parno, S. Zahur. Geppetto: versatile verifiable computation, in Proceedings of the 36th IEEE symposium on security and privacy, S&P \u201915, 2015, pp. 253\u2013270.","DOI":"10.1109\/SP.2015.23"},{"key":"9241_CR39","doi-asserted-by":"crossref","unstructured":"M. Chase, M. Kohlweiss, A. Lysyanskaya, S. Meiklejohn, Succinct malleable nizks and an application to compact shuffles, in TCC, 2013, pp. 100\u2013119.","DOI":"10.1007\/978-3-642-36594-2_6"},{"key":"9241_CR40","doi-asserted-by":"crossref","unstructured":"K.-M. Chung, Y. Kalai, F.-H. Liu, R. Raz. Memory delegation, in Proceeding of the 31st annual cryptology conference, 2011, pp. 151\u2013168.","DOI":"10.1007\/978-3-642-22792-9_9"},{"key":"9241_CR41","doi-asserted-by":"crossref","unstructured":"R. Canetti, J. Kilian, E. Petrank, A. Rosen, Black-box concurrent zero-knowledge requires $$\\tilde{\\omega }(\\log n)$$ \u03c9 ~ ( log n ) rounds, in STOC \u201901, 2001, pp. 570\u2013579.","DOI":"10.1145\/380752.380852"},{"key":"9241_CR42","doi-asserted-by":"crossref","unstructured":"K.-M. Chung, Y. Kalai, S. Vadhan, Improved delegation of computation using fully homomorphic encryption, in Proceedings of the 30th annual international cryptology conference, 2010, pp. 483\u2013501.","DOI":"10.1007\/978-3-642-14623-7_26"},{"key":"9241_CR43","doi-asserted-by":"crossref","unstructured":"C. Cachin, S. Micali, M. Stadler, Computationally private information retrieval with polylogarithmic communication, in Proceedings of the international conference on the theory and application of cryptographic techniques, 1999, pp. 402\u2013414.","DOI":"10.1007\/3-540-48910-X_28"},{"key":"9241_CR44","unstructured":"R. Canetti, B. Riva, G.N. Rothblum, Two 1-round protocols for delegation of computation. Cryptology ePrint Archive, Report 2011\/518, 2011."},{"key":"9241_CR45","unstructured":"A. Chiesa, E. Tromer, Proof-carrying data and hearsay arguments from signature cards, in Proceedings of the 1st symposium on innovations in computer science, 2010, pp. 310\u2013331."},{"key":"9241_CR46","unstructured":"G. Cormode, J. Thaler, K.\u00a0Yi, Verifying computations with streaming interactive proofs. Technical report, 2010. ECCC TR10-159."},{"key":"9241_CR47","unstructured":"R.R. Dakdouk, Theory and application of extractable functions. Ph.D. thesis, Yale University, Computer Science Department, December 2009."},{"key":"9241_CR48","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, Towards practical public key systems secure against chosen ciphertext attacks, in Proceedings of the 11th annual international cryptology conference, 1992, pp. 445\u2013456.","DOI":"10.1007\/3-540-46766-1_36"},{"key":"9241_CR49","doi-asserted-by":"crossref","unstructured":"G. Di\u00a0Crescenzo, H. Lipmaa, Succinct NP proofs from an extractability assumption, in Proceedings of the 4th conference on computability in Europe, 2008, pp. 175\u2013185.","DOI":"10.1007\/978-3-540-69407-6_21"},{"key":"9241_CR50","unstructured":"A.W. Dent, The hardness of the DHK problem in the generic group model. Cryptology ePrint Archive, Report 2006\/156, 2006."},{"key":"9241_CR51","doi-asserted-by":"crossref","unstructured":"G. Danezis, C. Fournet, J. Groth, M. Kohlweiss, Square span programs with applications to succinct NIZK arguments, in Proceedings of the 20th international conference on the theory and application of cryptology and information security, ASIACRYPT\u00a0\u201914, 2014, pp. 532\u2013550.","DOI":"10.1007\/978-3-662-45611-8_28"},{"key":"9241_CR52","doi-asserted-by":"crossref","unstructured":"I. Damg\u00e5rd, S. Faust, C. Hazay, Secure two-party computation with low communication. Cryptology ePrint Archive, Report 2011\/508, 2011.","DOI":"10.1007\/978-3-642-28914-9_4"},{"key":"9241_CR53","unstructured":"A. Dent, S. Galbraith, Hidden pairings and trapdoor DDH groups, in F. Hess, S. Pauli, M. Pohst, editors, Algorithmic number theory, vol. 4076 of lecture notes in computer science, 2006, pp. 436\u2013451."},{"key":"9241_CR54","doi-asserted-by":"crossref","unstructured":"Y.\u00a0Deng, V. Goyal, A. Sahai, Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy, in FOCS, 2009, pp. 251\u2013260.","DOI":"10.1109\/FOCS.2009.59"},{"key":"9241_CR55","doi-asserted-by":"crossref","unstructured":"S. Dziembowski, P. Krzysztof, Leakage-resilient cryptography, in Proceedings of the 49th annual IEEE symposium on foundations of computer science, 2008, pp. 293\u2013302.","DOI":"10.1109\/FOCS.2008.56"},{"key":"9241_CR56","unstructured":"C. Dwork, M. Langberg, M. Naor, K. Nissim, O. Reingold. Succinct NP proofs and spooky interactions, December 2004. Available at www.openu.ac.il\/home\/mikel\/papers\/spooky.ps ."},{"key":"9241_CR57","doi-asserted-by":"crossref","unstructured":"C. Dwork, M. Naor, Zaps and their applications, in FOCS, 2000, pp. 283\u2013293","DOI":"10.1109\/SFCS.2000.892117"},{"issue":"6","key":"9241_CR58","doi-asserted-by":"publisher","first-page":"852","DOI":"10.1145\/950620.950623","volume":"50","author":"C Dwork","year":"2003","unstructured":"Cynthia Dwork, Moni Naor, Omer Reingold, and Larry\u00a0J. Stockmeyer. Magic functions. J. ACM, 50(6):852\u2013921, 2003.","journal-title":"J. ACM"},{"key":"9241_CR59","doi-asserted-by":"crossref","unstructured":"Y. Dodis, T. Ristenpart, T. Shrimpton, Salvaging merkle-damg\u00e5rd for practical applications, in Proceedings of the 28th annual international conference on the theory and applications of cryptographic techniques, 2009, pp. 371\u2013388.","DOI":"10.1007\/978-3-642-01001-9_22"},{"key":"9241_CR60","unstructured":"B. Ederov, Merkle tree traversal techniques. Ph.D. thesis, Darmstadt University of Technology, Department of Computer Science, April 2007"},{"key":"9241_CR61","doi-asserted-by":"crossref","unstructured":"P. Fauzi, H. Lipmaa, B. Zhang, Efficient modular NIZK arguments from shift and product, in Proceedings of the 12th international conference on cryptology and network security, CANS \u201913, 2013, pp. 92\u2013121.","DOI":"10.1007\/978-3-319-02937-5_6"},{"key":"9241_CR62","doi-asserted-by":"crossref","unstructured":"A. Fiat, A. Shamir, How to prove yourself: practical solutions to identification and signature problems, in Proceedings of the 6th annual international cryptology conference, 1987, pp. 186\u2013194","DOI":"10.1007\/3-540-47721-7_12"},{"key":"9241_CR63","doi-asserted-by":"crossref","unstructured":"C. Gentry, Fully homomorphic encryption using ideal lattices, in Proceedings of the 41st annual ACM symposium on theory of computing, 2009, pp. 169\u2013178","DOI":"10.1145\/1536414.1536440"},{"key":"9241_CR64","unstructured":"O. Goldreich, S. Goldwasser, S. Halevi, Collision-free hashing from lattice problems. Technical report, 1996. ECCC TR95-042"},{"key":"9241_CR65","doi-asserted-by":"crossref","unstructured":"R. Gennaro, C. Gentry, B. Parno. Non-interactive verifiable computing: outsourcing computation to untrusted workers, in Proceedings of the 30th annual international cryptology conference, 2010, pp. 465\u2013482.","DOI":"10.1007\/978-3-642-14623-7_25"},{"key":"9241_CR66","doi-asserted-by":"crossref","unstructured":"R. Gennaro, C. Gentry, B. Parno, M. Raykova, Quadratic span programs and succinct NIZKs without PCPs, in Proceedings of the 32nd annual international conference on theory and application of cryptographic techniques, EUROCRYPT\u00a0\u201913, 2013, pp. 626\u2013645","DOI":"10.1007\/978-3-642-38348-9_37"},{"issue":"4","key":"9241_CR67","doi-asserted-by":"publisher","first-page":"205","DOI":"10.1016\/S0020-0190(98)00116-1","volume":"67","author":"O Goldreich","year":"1998","unstructured":"Oded Goldreich and Johan H\u00e5stad. On the complexity of interactive proofs with bounded communication. Information Processing Letters, 67(4):205\u2013214, 1998.","journal-title":"Inf. Process. Lett."},{"issue":"1","key":"9241_CR68","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1137\/S0097539791220688","volume":"25","author":"O Goldreich","year":"1996","unstructured":"Oded Goldreich and Hugo Krawczyk. On the composition of zero-knowledge proof systems. SIAM Journal on Computing, 25(1):169\u2013192, 1996.","journal-title":"SIAM J. Comput."},{"key":"9241_CR69","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, Y.T. Kalai, G.N. Rothblum, Delegating computation: interactive proofs for Muggles, in Proceedings of the 40th annual ACM symposium on theory of computing, 2008, pp. 113\u2013122.","DOI":"10.1145\/1374376.1374396"},{"key":"9241_CR70","doi-asserted-by":"crossref","unstructured":"R. Gennaro, H. Krawczyk, T. Rabin, Okamoto\u2013Tanaka revisited: fully authenticated Diffie\u2013Hellman with minimal overhead, in Proceedings of the 8th international conference on applied cryptography and network security, 2010, pp. 309\u2013328","DOI":"10.1007\/978-3-642-13708-2_19"},{"key":"9241_CR71","unstructured":"S. Goldwasser, H. Lin, A. Rubinstein, Delegation of computation without rejection problem from designated verifier CS-proofs. Cryptology ePrint Archive, Report 2011\/456, 2011."},{"issue":"2","key":"9241_CR72","doi-asserted-by":"publisher","first-page":"270","DOI":"10.1016\/0022-0000(84)90070-9","volume":"28","author":"S Goldwasser","year":"1984","unstructured":"Shafi Goldwasser and Silvio Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270\u2013299, 1984.","journal-title":"J. Comput. Syst. Sci."},{"key":"9241_CR73","doi-asserted-by":"crossref","unstructured":"S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1), pp. 186\u2013208, 1989. Preliminary version appeared in STOC\u00a0\u201985","DOI":"10.1137\/0218012"},{"issue":"3","key":"9241_CR74","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O Goldreich","year":"1991","unstructured":"Oded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that yield nothing but their validity for all languages in NP have zero-knowledge proof systems. J. ACM, 38(3):691\u2013729, 1991.","journal-title":"J. ACM"},{"key":"9241_CR75","doi-asserted-by":"crossref","unstructured":"N. Gama, P.Q. Nguyen. Predicting lattice reduction, in Proceedings of the 27th annual international conference on the theory and applications of cryptographic techniques, 2008, pp. 31\u201351","DOI":"10.1007\/978-3-540-78967-3_3"},{"issue":"1","key":"9241_CR76","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00195207","volume":"7","author":"O Goldreich","year":"1994","unstructured":"Oded Goldreich and Yair Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 7(1):1\u201332, December 1994.","journal-title":"J. Cryptol."},{"key":"9241_CR77","doi-asserted-by":"crossref","unstructured":"O. Goldreich, The foundations of cryptography\u2014volume 1, basic techniques. Cambridge University Press, 2001","DOI":"10.1017\/CBO9780511546891"},{"key":"9241_CR78","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511546891","volume-title":"Foundations of cryptography: basic tools","author":"O Goldreich","year":"2001","unstructured":"Oded Goldreich. Foundations of Cryptography: Basic Tools, volume\u00a01. Cambridge University Press, New York, NY, USA, 2001."},{"key":"9241_CR79","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511721656","volume-title":"Foundations of cryptography: basic applications","author":"O Goldreich","year":"2004","unstructured":"Oded Goldreich. Foundations of Cryptography: Basic Applications, volume\u00a02. Cambridge University Press, New York, NY, USA, 2004."},{"key":"9241_CR80","doi-asserted-by":"crossref","unstructured":"C. Gentry, Z. Ramzan. Single-database private information retrieval with constant communication rate, in Proceedings of the 32nd international colloquium on automata, languages and programming, 2005, pp. 803\u2013815","DOI":"10.1007\/11523468_65"},{"key":"9241_CR81","doi-asserted-by":"crossref","unstructured":"J. Groth. Short pairing-based non-interactive zero-knowledge arguments, in Proceedings of the 16th international conference on the theory and application of cryptology and information security, 2010, pp. 321\u2013340","DOI":"10.1007\/978-3-642-17373-8_19"},{"key":"9241_CR82","unstructured":"D. Gupta, A. Sahai, On constant-round concurrent zero-knowledge from a knowledge assumption. Cryptology ePrint Archive, Report 2012\/572, 2012. http:\/\/eprint.iacr.org\/"},{"issue":"1\/2","key":"9241_CR83","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-002-0169-0","volume":"11","author":"O Goldreich","year":"2002","unstructured":"Oded Goldreich, Salil Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. Computational Complexity, 11(1\/2):1\u201353, 2002.","journal-title":"Comput. Complex."},{"key":"9241_CR84","doi-asserted-by":"crossref","unstructured":"C. Gentry, D. Wichs, Separating succinct non-interactive arguments from all falsifiable assumptions, in Proceedings of the 43rd annual ACM symposium on theory of computing, 2011, pp. 99\u2013108.","DOI":"10.1145\/1993636.1993651"},{"key":"9241_CR85","doi-asserted-by":"crossref","unstructured":"I. Haitner, D. Harnik, O. Reingold. Efficient pseudorandom generators from exponentially hard one-way functions, in Proceedings of the 33rd international colloquium on automata, languages and programming, 2006, pp. 228\u2013239","DOI":"10.1007\/11787006_20"},{"issue":"4","key":"9241_CR86","doi-asserted-by":"publisher","first-page":"1364","DOI":"10.1137\/S0097539793244708","volume":"28","author":"J H\u00e5stad","year":"1999","unstructured":"Johan H\u00e5stad, Russell Impagliazzo, Leonid\u00a0A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364\u20131396, 1999.","journal-title":"SIAM J Comput"},{"key":"9241_CR87","doi-asserted-by":"crossref","unstructured":"S. Hada, T. Tanaka, On the existence of 3-round zero-knowledge protocols, in Proceedings of the 18th annual international cryptology conference, 1998, pp. 408\u2013423","DOI":"10.1007\/BFb0055744"},{"key":"9241_CR88","doi-asserted-by":"crossref","unstructured":"Y. Ishai, E. Kushilevitz, R. Ostrovsky, M. Prabhakaran, A. Sahai, Efficient non-interactive secure computation, in Proceedings of the 30th annual international conference on the theory and applications of cryptographic techniques, 2011, pp. 406\u2013425","DOI":"10.1007\/978-3-642-20465-4_23"},{"key":"9241_CR89","doi-asserted-by":"crossref","unstructured":"J. Kilian. A note on efficient zero-knowledge proofs and arguments, in Proceedings of the 24th annual ACM symposium on theory of computing, 1992, pp. 723\u2013732","DOI":"10.1145\/129712.129782"},{"key":"9241_CR90","doi-asserted-by":"crossref","unstructured":"E. Kushilevitz, R. Ostrovsky. Replication is NOT needed: SINGLE database, computationally-private information retrieval, in 38th annual symposium on foundations of computer science, FOCS \u201997, Miami Beach, Florida, USA, October 19\u201322, 1997, 1997, pp. 364\u2013373","DOI":"10.1109\/SFCS.1997.646125"},{"key":"9241_CR91","unstructured":"Y.T. Kalai, O. Paneth. Delegating RAM computations. Cryptology ePrint Archive, Report 2015\/957, 2015"},{"key":"9241_CR92","unstructured":"A.E. Kosba, D. Papadopoulos, C. Papamanthou, M.F. Sayed, E. Shi, N. Triandopoulos, TRUESET: Faster verifiable set computations, in Proceedings of the 23rd USENIX security symposium, USENIX Security\u00a0\u201914, 2014, pp 765\u2013780"},{"key":"9241_CR93","doi-asserted-by":"crossref","unstructured":"Y.T. Kalai, R. Raz, Succinct non-interactive zero-knowledge proofs with preprocessing for LOGSNP, in Proceedings of the 47th annual IEEE symposium on foundations of computer science, 2006, pp. 355\u2013366","DOI":"10.1109\/FOCS.2006.74"},{"key":"9241_CR94","doi-asserted-by":"crossref","unstructured":"Y.T. Kalai, R. Raz, Probabilistically checkable arguments, in Proceedings of the 29th annual international cryptology conference, 2009, pp. 143\u2013159","DOI":"10.1007\/978-3-642-03356-8_9"},{"key":"9241_CR95","unstructured":"Y. Kalai, R. Raz, R. Rothblum, Delegation for bounded space, in Proceedings of the 45th ACM symposium on the theory of computing, STOC\u00a0\u201913, 2013, pp. 565\u2013574"},{"key":"9241_CR96","doi-asserted-by":"crossref","unstructured":"Y.T. Kalai, R. Raz, R.D. Rothblum, How to delegate computations: the power of no-signaling proofs, in Proceedings of the 46th annual ACM symposium on theory of computing, STOC \u201914, 2014, pp. 485\u2013494","DOI":"10.1145\/2591796.2591809"},{"key":"9241_CR97","doi-asserted-by":"crossref","unstructured":"H. Lipmaa, Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments, in Proceedings of the 9th theory of cryptography conference on theory of cryptography, TCC\u00a0\u201912, 2012, pp. 169\u2013189","DOI":"10.1007\/978-3-642-28914-9_10"},{"key":"9241_CR98","doi-asserted-by":"crossref","unstructured":"H. Lipmaa, Succinct non-interactive zero knowledge arguments from span programs and linear error-correcting codes, in Proceedings of the 19th international conference on the theory and application of cryptology and information security, ASIACRYPT\u00a0\u201913, 2013, pp. 41\u201360","DOI":"10.1007\/978-3-642-42033-7_3"},{"key":"9241_CR99","doi-asserted-by":"crossref","unstructured":"H. Lipmaa, Efficient NIZK arguments via parallel verification of Bene\u0161 networks, in Proceedings of the 9th international conference on security and cryptography for networks, SCN \u201914, 2014, pp. 416\u2013434","DOI":"10.1007\/978-3-319-10879-7_24"},{"key":"9241_CR100","doi-asserted-by":"crossref","unstructured":"V. Lyubashevsky, D. Micciancio, On bounded distance decoding, unique shortest vectors, and the minimum distance problem, in Proceedings of the 29th annual international cryptology conference, 2009, pp. 577\u2013594","DOI":"10.1007\/978-3-642-03356-8_34"},{"key":"9241_CR101","doi-asserted-by":"crossref","unstructured":"D. Lapidot, A. Shamir, Publicly verifiable non-interactive zero-knowledge proofs, in CRYPTO, 1990, pp. 353\u2013365","DOI":"10.1007\/3-540-38424-3_26"},{"key":"9241_CR102","unstructured":"R. Merkle, Secrecy, authentication and public key systems. Ph.D. thesis, Stanford University, Department of Electrical Engineering, 1979"},{"key":"9241_CR103","doi-asserted-by":"crossref","unstructured":"R.C. Merkle, A certified digital signature, in Proceedings of the 9th annual international cryptology conference, 1989, pp. 218\u2013238","DOI":"10.1007\/0-387-34805-0_21"},{"key":"9241_CR104","unstructured":"S. Micali, Computationally sound proofs. SIAM J. Comput., 30(4), pp. 1253\u20131298, 2000. Preliminary version appeared in FOCS\u00a0\u201994."},{"issue":"4","key":"9241_CR105","doi-asserted-by":"publisher","first-page":"343","DOI":"10.1515\/JMC.2008.016","volume":"2","author":"T Mie","year":"2008","unstructured":"Thilo Mie. Polylogarithmic two-round argument systems. Journal of Mathematical Cryptology, 2(4):343\u2013363, 2008.","journal-title":"J. Math. Cryptol."},{"key":"9241_CR106","doi-asserted-by":"publisher","first-page":"267","DOI":"10.1137\/S0097539705447360","volume":"37","author":"D Micciancio","year":"2007","unstructured":"Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. SIAM Journal on Computing, 37:267\u2013302, April 2007.","journal-title":"SIAM J. Comput."},{"key":"9241_CR107","doi-asserted-by":"crossref","unstructured":"M. Naor, On cryptographic assumptions and challenges, in Proceedings of the 23rd annual international cryptology conference, 2003, pp. 96\u2013109","DOI":"10.1007\/978-3-540-45146-4_6"},{"key":"9241_CR108","unstructured":"V.I. Nechaev, Complexity of a determinate algorithm for the discrete logarithm. Mathematical Notes, 55, (1994), pp. 165\u2013172"},{"key":"9241_CR109","doi-asserted-by":"crossref","unstructured":"M. Naor, K. Nissim, Communication preserving protocols for secure function evaluation, in Proceedings of the 33rd annual ACM symposium on theory of computing, 2001, pp. 590\u2013599","DOI":"10.1145\/380752.380855"},{"issue":"4","key":"9241_CR110","doi-asserted-by":"publisher","first-page":"481","DOI":"10.1109\/49.17711","volume":"7","author":"E Okamoto","year":"1989","unstructured":"Eiji Okamoto and Kazue Tanaka. Key distribution system based on identification information. Selected Areas in Communications, IEEE Journal on, 7(4):481\u2013485, May 1989.","journal-title":"IEEE J. Sel. Areas Commun."},{"key":"9241_CR111","doi-asserted-by":"crossref","unstructured":"R. Pass, Limits of provable security from standard assumptions, in STOC, 2011, pp. 109\u2013118","DOI":"10.1145\/1993636.1993652"},{"key":"9241_CR112","doi-asserted-by":"crossref","unstructured":"B. Parno, C. Gentry, J. Howell, M. Raykova, Pinocchio: nearly practical verifiable computation, in Proceedings of the 34th IEEE symposium on security and privacy, Oakland\u00a0\u201913, 2013, pp. 238\u2013252","DOI":"10.1109\/SP.2013.47"},{"key":"9241_CR113","unstructured":"O. Paneth, G.N. Rothblum. Publicly verifiable non-interactive arguments for delegating computation. Cryptology ePrint Archive, Report 2014\/981, 2014"},{"key":"9241_CR114","doi-asserted-by":"crossref","unstructured":"C. Papamanthou, E. Shi, R. Tamassia, K.\u00a0Yi, Streaming authenticated data structures, in Proceedings of the international conference on the theory and application of cryptographic techniques, 2013, pp. 353\u2013370","DOI":"10.1007\/978-3-642-38348-9_22"},{"key":"9241_CR115","doi-asserted-by":"crossref","unstructured":"C. Papamanthou, R. Tamassia, N. Triandopoulos, Optimal verification of operations on dynamic sets, in Proceeding of the 31st annual cryptology conference, 2011, pp. 91\u2013110","DOI":"10.1007\/978-3-642-22792-9_6"},{"key":"9241_CR116","doi-asserted-by":"crossref","unstructured":"M. Prabhakaran, R. Xue. Statistically hiding sets, in Proceedings of the cryptographers\u2019 track at the RSA conference 2009, 2009, pp. 100\u2013116","DOI":"10.1007\/978-3-642-00862-7_7"},{"key":"9241_CR117","doi-asserted-by":"crossref","unstructured":"O. Regev, New lattice based cryptographic constructions, in Proceedings of the 35th annual ACM symposium on theory of computing, 2003, pp. 407\u2013416","DOI":"10.1145\/780542.780603"},{"issue":"6","key":"9241_CR118","doi-asserted-by":"publisher","first-page":"899","DOI":"10.1145\/1039488.1039490","volume":"51","author":"O Regev","year":"2004","unstructured":"Oded Regev. New lattice-based cryptographic constructions. Journal of the ACM, 51(6):899\u2013942, 2004.","journal-title":"J ACM"},{"key":"9241_CR119","doi-asserted-by":"crossref","unstructured":"O. Regev, On lattices, learning with errors, random linear codes, and cryptography, in Proceedings of the 37th annual ACM symposium on theory of computing, 2005, pp. 84\u201393","DOI":"10.1145\/1060590.1060603"},{"key":"9241_CR120","first-page":"204","volume":"55","author":"AA Razborov","year":"1994","unstructured":"Alexander\u00a0A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55:204\u2013213, 1994.","journal-title":"J Comput Syst Sci"},{"key":"9241_CR121","doi-asserted-by":"crossref","unstructured":"O. Reingold, L. Trevisan, M. Tulsiani, S.P. Vadhan, Dense subsets of pseudorandom sets, in Proceedings of the 49th annual IEEE symposium on foundations of computer science, 2008, pp. 76\u201385","DOI":"10.1109\/FOCS.2008.38"},{"issue":"4","key":"9241_CR122","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A Shamir","year":"1992","unstructured":"Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869\u2013877, 1992.","journal-title":"J ACM"},{"key":"9241_CR123","doi-asserted-by":"crossref","unstructured":"V. Shoup, Lower bounds for discrete logarithms and related problems, in Proceedings of the international conference on the theory and application of cryptographic techniques, 1997, pp. 256\u2013266","DOI":"10.1007\/3-540-69053-0_18"},{"key":"9241_CR124","doi-asserted-by":"crossref","unstructured":"P. Valiant, Incrementally verifiable computation or proofs of knowledge imply time\/space efficiency, in Proceedings of the 5th theory of cryptography conference, 2008, pp. 1\u201318","DOI":"10.1007\/978-3-540-78524-8_1"},{"key":"9241_CR125","doi-asserted-by":"crossref","unstructured":"H. Wee, On round-efficient argument systems, in Proceedings of the 32nd international colloquium on automata, languages and programming, 2005, pp. 140\u2013152","DOI":"10.1007\/11523468_12"},{"key":"9241_CR126","doi-asserted-by":"crossref","unstructured":"R.S. Wahby, S. Setty, Z. Ren, A.J. Blumberg, M. Walfish, Efficient RAM and control flow in verifiable outsourced computation, in Proceedings of the 22nd network and distributed system security symposium, NDSS\u00a0\u201915, 2015","DOI":"10.14722\/ndss.2015.23097"},{"key":"9241_CR127","doi-asserted-by":"crossref","unstructured":"Y. Zhang, C. Papamanthou, J. Katz, Alitheia: towards practical verifiable graph processing, in Proceedings of the 21st ACM conference on computer and communications security, CCS \u201914, 2014, pp. 856\u2013867","DOI":"10.1145\/2660267.2660354"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-016-9241-9\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9241-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-016-9241-9.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,10]],"date-time":"2025-06-10T22:30:47Z","timestamp":1749594647000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-016-9241-9"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,10,3]]},"references-count":127,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2017,10]]}},"alternative-id":["9241"],"URL":"https:\/\/doi.org\/10.1007\/s00145-016-9241-9","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"value":"0933-2790","type":"print"},{"value":"1432-1378","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,10,3]]},"assertion":[{"value":"5 August 2014","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"18 April 2016","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"3 October 2016","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}