×

The hunting of the SNARK. (English) Zbl 1386.94066

Summary: 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 non-deterministic verifier) has been an intriguing question for the past two decades. Other than CS proofs in the random oracle model [S. Micali, SIAM J. Comput. 30, No. 4, 1253–1298 (2000; Zbl 1009.68053)], prior to our work the only existing candidate construction is based on an elaborate assumption that is tailored to a specific protocol [G. Di Crescenzo and H. Lipmaa, CiE 2008, Lect. Notes Comput. Sci. 5028, 175–185 (2008; Zbl 1142.68370)]. We formulate a general and relatively natural notion of an extractable collision-resistant hash function (ECRH) and show that, if ECRHs exist, then a modified version of Di Crescenzo and Lipmaa’s protocol is a succinct non-interactive argument for NP. Furthermore, the modified protocol is actually a succinct non-interactive adaptive argument of knowledge (SNARK). We then propose several candidate constructions for ECRHs and relaxations thereof. We demonstrate the applicability of SNARKs to various forms of delegation of computation, to succinct non-interactive zero-knowledge arguments, and to succinct two-party secure computation. Finally, we show that SNARKs essentially imply the existence of ECRHs, thus demonstrating the necessity of the assumption. Going beyond ECRHs, we formulate the notion of extractable one-way functions (EOWFs). Assuming the existence of a natural variant of EOWFs, we construct a two-message selective-opening-attack-secure commitment scheme and a three-round zero-knowledge argument of knowledge. Furthermore, if the EOWFs are concurrently extractable, the three-round zero-knowledge protocol is also concurrent zero knowledge. Our constructions circumvent previous black-box impossibility results regarding these protocols by relying on EOWFs as the non-black-box component in the security reductions.
This paper is a merge of [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/] and [S. Goldwasser, H. Lin, A. Rubinstein, Delegation of computation without rejection problem from designated verifier CS-proofs. Cryptology ePrint Archive, Report 2011/456, 2011]. A preliminary version including part of the results appeared in [ITCS 2012, New York, NY: ACM, 326–349 (2012; Zbl 1347.68129)].

MSC:

94A60 Cryptography
68Q05 Models of computation (Turing machines, etc.) (MSC2010)
68Q10 Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.)
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] 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-474. · Zbl 0973.68523
[2] 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-6, 2009. Revised Selected Papers, 2009, pp. 1-18. · Zbl 1282.94031
[3] M. Abe, S. Fehr. Perfect NIZK with adaptive soundness, in Proceedings of the 4th theory of cryptography conference, 2007, pp. 118-136. · Zbl 1129.94008
[4] 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-163. · Zbl 1287.68041
[5] M. Ajtai. Generating hard instances of lattice problems, in Proceedings of the 28th annual ACM symposium on the theory of computing, 1996, pp. 99-108. · Zbl 0921.11071
[6] 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-555. · Zbl 1065.68570
[7] S. Arora, S. Safra, Probabilistic checking of proofs: a new characterization of NP. J. ACM, 45(1), (1998) pp. 70-122 · Zbl 0903.68076
[8] 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 ’15, 2015, pp. 271-286. · Zbl 0799.68096
[9] 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 ’12, 2012, pp. 255-272. · Zbl 1296.94090
[10] Gilles Brassard, David Chaum, and Claude Crépeau. Minimum disclosure proofs of knowledge. Journal of Computer and System Sciences, 37(2):156-189, 1988. · Zbl 0656.68109 · doi:10.1016/0022-0000(88)90005-0
[11] 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/. · Zbl 1347.68129
[12] 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 ’12, 2012, pp. 326-349. · Zbl 1347.68129
[13] 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 ’13, 2013, pp. 111-120. · Zbl 1293.68264
[14] 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 ’13, 2013, pp. 90-108. · Zbl 1317.68050
[15] 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 ’13, 2013, pp. 315-333. · Zbl 1316.68056
[16] N. Bitansky, R. Canetti, O. Paneth, A. Rosen, On the existence of extractable one-way functions, in STOC, 2014. · Zbl 1315.94059
[17] 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 ’14, pp. 276-294, 2014. Extended version at http://eprint.iacr.org/2014/595. · Zbl 1334.68077
[18] 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 ’14, pp. 781-796, 2014. Extended version at http://eprint.iacr.org/2013/879. · Zbl 1334.68077
[19] 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-4, 1988, Chicago, IL, USA, 1988, pp. 103-112. · Zbl 0791.94010
[20] B. Barak, O. Goldreich. Universal arguments and their applications. SIAM J. Comput.38(5), pp. 1661-1694, 2008. Preliminary version appeared in CCC ’02. · Zbl 1180.94047
[21] B. Barak, O. Goldreich, S. Goldwasser, Y. Lindell. Resettably-sound zero-knowledge and its applications, in FOCS, 2001, pp. 116-125.
[22] B. Barak, O. Goldreich, R. Impagliazzo, S. Rudich, A. Sahai, S.P. Vadhan, K. Yang. On the (im)possibility of obfuscating programs, SIAM J. Comput., 59(2), 2012. · Zbl 1281.68118
[23] 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-131. · Zbl 1288.68159
[24] 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-366. · Zbl 1125.94026
[25] Ravi B. Boppana, Johan Håstad, and Stathis Zachos. Does co-NP have short interactive proofs? Information Processing Letters, 25(2):127-132, 1987. · Zbl 0653.68037 · doi:10.1016/0020-0190(87)90232-8
[26] M. Blum. Coin flipping by telephone, in Proceedings of the 18th annual international cryptology conference, 1981, pp. 11-15. · Zbl 0799.68101
[27] 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-289. · Zbl 1104.94043
[28] E. Boyle, R. Pass, Limits of extractability assumptions with distributional auxiliary input. Cryptology ePrint Archive, Report 2013/703, 2013. http://eprint.iacr.org/. · Zbl 1375.94106
[29] 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 ’13, 2013. · Zbl 1293.94054
[30] 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-134.
[31] Eli Ben-Sasson and Madhu Sudan. Short PCPs with polylog query complexity. SIAM Journal on Computing, 38(2):551-607, 2008. · Zbl 1172.68025 · doi:10.1137/050646445
[32] D. Boneh, G. Segev, B. Waters. Targeted malleability: Homomorphic encryption for restricted computations. Cryptology ePrint Archive, Report 2011/311, 2011. · Zbl 1347.68119
[33] 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. · Zbl 1292.94038
[34] 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-469. · Zbl 0884.68048
[35] 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-145. · Zbl 0799.68096
[36] 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-460. · Zbl 1155.94364
[37] R. Canetti, R.R. Dakdouk, Towards a theory of extractable functions, in Proceedings of the 6th theory of cryptography conference, 2009, pp. 595-613. · Zbl 1213.94089
[38] 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 ’15, 2015, pp. 253-270.
[39] M. Chase, M. Kohlweiss, A. Lysyanskaya, S. Meiklejohn, Succinct malleable nizks and an application to compact shuffles, in TCC, 2013, pp. 100-119. · Zbl 1297.94058
[40] K.-M. Chung, Y. Kalai, F.-H. Liu, R. Raz. Memory delegation, in Proceeding of the 31st annual cryptology conference, 2011, pp. 151-168. · Zbl 1288.68005
[41] R. Canetti, J. Kilian, E. Petrank, A. Rosen, Black-box concurrent zero-knowledge requires \[\tilde{\omega }(\log n)\] ω (logn) rounds, in STOC ’01, 2001, pp. 570-579. · Zbl 1317.68064
[42] 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-501. · Zbl 1284.68063
[43] 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-414. · Zbl 0932.68042
[44] R. Canetti, B. Riva, G.N. Rothblum, Two 1-round protocols for delegation of computation. Cryptology ePrint Archive, Report 2011/518, 2011. · Zbl 1295.94030
[45] 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-331.
[46] G. Cormode, J. Thaler, K. Yi, Verifying computations with streaming interactive proofs. Technical report, 2010. ECCC TR10-159.
[47] R.R. Dakdouk, Theory and application of extractable functions. Ph.D. thesis, Yale University, Computer Science Department, December 2009. · Zbl 1213.94089
[48] I. Damgård, Towards practical public key systems secure against chosen ciphertext attacks, in Proceedings of the 11th annual international cryptology conference, 1992, pp. 445-456. · Zbl 0764.94015
[49] G. Di Crescenzo, H. Lipmaa, Succinct NP proofs from an extractability assumption, in Proceedings of the 4th conference on computability in Europe, 2008, pp. 175-185. · Zbl 1142.68370
[50] A.W. Dent, The hardness of the DHK problem in the generic group model. Cryptology ePrint Archive, Report 2006/156, 2006.
[51] 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 ’14, 2014, pp. 532-550. · Zbl 1306.94042
[52] I. Damgård, S. Faust, C. Hazay, Secure two-party computation with low communication. Cryptology ePrint Archive, Report 2011/508, 2011. · Zbl 1303.94076
[53] 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-451. · Zbl 1143.94344
[54] Y. Deng, V. Goyal, A. Sahai, Resolving the simultaneous resettability conjecture and a new non-black-box simulation strategy, in FOCS, 2009, pp. 251-260. · Zbl 1292.94054
[55] S. Dziembowski, P. Krzysztof, Leakage-resilient cryptography, in Proceedings of the 49th annual IEEE symposium on foundations of computer science, 2008, pp. 293-302.
[56] 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.
[57] C. Dwork, M. Naor, Zaps and their applications, in FOCS, 2000, pp. 283-293 · Zbl 1125.94019
[58] Cynthia Dwork, Moni Naor, Omer Reingold, and Larry J. Stockmeyer. Magic functions. J. ACM, 50(6):852-921, 2003. · Zbl 1325.68034 · doi:10.1145/950620.950623
[59] Y. Dodis, T. Ristenpart, T. Shrimpton, Salvaging merkle-damgård for practical applications, in Proceedings of the 28th annual international conference on the theory and applications of cryptographic techniques, 2009, pp. 371-388. · Zbl 1239.94047
[60] B. Ederov, Merkle tree traversal techniques. Ph.D. thesis, Darmstadt University of Technology, Department of Computer Science, April 2007 · Zbl 1172.68025
[61] 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 ’13, 2013, pp. 92-121. · Zbl 0841.68112
[62] 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-194 · Zbl 0636.94012
[63] C. Gentry, Fully homomorphic encryption using ideal lattices, in Proceedings of the 41st annual ACM symposium on theory of computing, 2009, pp. 169-178 · Zbl 1304.94059
[64] O. Goldreich, S. Goldwasser, S. Halevi, Collision-free hashing from lattice problems. Technical report, 1996. ECCC TR95-042 · Zbl 1343.94055
[65] 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-482. · Zbl 1284.68065
[66] 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 ’13, 2013, pp. 626-645 · Zbl 1300.94056
[67] Oded Goldreich and Johan Håstad. On the complexity of interactive proofs with bounded communication. Information Processing Letters, 67(4):205-214, 1998. · Zbl 1338.68104 · doi:10.1016/S0020-0190(98)00116-1
[68] Oded Goldreich and Hugo Krawczyk. On the composition of zero-knowledge proof systems. SIAM Journal on Computing, 25(1):169-192, 1996. · Zbl 0841.68112 · doi:10.1137/S0097539791220688
[69] 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-122. · Zbl 1231.68135
[70] R. Gennaro, H. Krawczyk, T. Rabin, Okamoto-Tanaka revisited: fully authenticated Diffie-Hellman with minimal overhead, in Proceedings of the 8th international conference on applied cryptography and network security, 2010, pp. 309-328 · Zbl 1350.94034
[71] S. Goldwasser, H. Lin, A. Rubinstein, Delegation of computation without rejection problem from designated verifier CS-proofs. Cryptology ePrint Archive, Report 2011/456, 2011.
[72] Shafi Goldwasser and Silvio Micali. Probabilistic encryption. J. Comput. Syst. Sci., 28(2):270-299, 1984. · Zbl 0563.94013 · doi:10.1016/0022-0000(84)90070-9
[73] S. Goldwasser, S. Micali, C. Rackoff, The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1), pp. 186-208, 1989. Preliminary version appeared in STOC ’85 · Zbl 0677.68062
[74] 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-729, 1991. · Zbl 0799.68101 · doi:10.1145/116825.116852
[75] 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-51 · Zbl 1149.94314
[76] Oded Goldreich and Yair Oren. Definitions and properties of zero-knowledge proof systems. Journal of Cryptology, 7(1):1-32, December 1994. · Zbl 0791.94010 · doi:10.1007/BF00195207
[77] O. Goldreich, The foundations of cryptography—volume 1, basic techniques. Cambridge University Press, 2001 · Zbl 1007.94016
[78] Oded Goldreich. Foundations of Cryptography: Basic Tools, volume 1. Cambridge University Press, New York, NY, USA, 2001. · Zbl 1007.94016 · doi:10.1017/CBO9780511546891
[79] Oded Goldreich. Foundations of Cryptography: Basic Applications, volume 2. Cambridge University Press, New York, NY, USA, 2004. · Zbl 1068.94011 · doi:10.1017/CBO9780511721656
[80] 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-815 · Zbl 1084.68043
[81] 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-340 · Zbl 1253.94049
[82] 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/ · Zbl 1344.94050
[83] Oded Goldreich, Salil Vadhan, and Avi Wigderson. On interactive proofs with a laconic prover. Computational Complexity, 11(1/2):1-53, 2002. · Zbl 1053.68045 · doi:10.1007/s00037-002-0169-0
[84] 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-108. · Zbl 1288.94063
[85] 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-239 · Zbl 1133.94319
[86] Johan Håstad, Russell Impagliazzo, Leonid A. Levin, and Michael Luby. A pseudorandom generator from any one-way function. SIAM Journal on Computing, 28(4):1364-1396, 1999. · Zbl 0940.68048 · doi:10.1137/S0097539793244708
[87] 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-423 · Zbl 0931.94009
[88] 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-425 · Zbl 1290.94151
[89] 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-732 · Zbl 0841.68112
[90] E. Kushilevitz, R. Ostrovsky. Replication is NOT needed: SINGLE database, computationally-private information retrieval, in 38th annual symposium on foundations of computer science, FOCS ’97, Miami Beach, Florida, USA, October 19-22, 1997, 1997, pp. 364-373
[91] Y.T. Kalai, O. Paneth. Delegating RAM computations. Cryptology ePrint Archive, Report 2015/957, 2015 · Zbl 1397.94074
[92] 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 ’14, 2014, pp 765-780
[93] 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-366
[94] Y.T. Kalai, R. Raz, Probabilistically checkable arguments, in Proceedings of the 29th annual international cryptology conference, 2009, pp. 143-159 · Zbl 1252.94079
[95] Y. Kalai, R. Raz, R. Rothblum, Delegation for bounded space, in Proceedings of the 45th ACM symposium on the theory of computing, STOC ’13, 2013, pp. 565-574 · Zbl 1293.68176
[96] 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 ’14, 2014, pp. 485-494 · Zbl 1315.68135
[97] 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 ’12, 2012, pp. 169-189 · Zbl 1303.94090
[98] 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 ’13, 2013, pp. 41-60 · Zbl 1300.94080
[99] H. Lipmaa, Efficient NIZK arguments via parallel verification of Beneš networks, in Proceedings of the 9th international conference on security and cryptography for networks, SCN ’14, 2014, pp. 416-434 · Zbl 1378.94054
[100] 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-594 · Zbl 1252.94084
[101] D. Lapidot, A. Shamir, Publicly verifiable non-interactive zero-knowledge proofs, in CRYPTO, 1990, pp. 353-365 · Zbl 0800.68414
[102] R. Merkle, Secrecy, authentication and public key systems. Ph.D. thesis, Stanford University, Department of Electrical Engineering, 1979 · Zbl 0549.94022
[103] R.C. Merkle, A certified digital signature, in Proceedings of the 9th annual international cryptology conference, 1989, pp. 218-238
[104] S. Micali, Computationally sound proofs. SIAM J. Comput., 30(4), pp. 1253-1298, 2000. Preliminary version appeared in FOCS ’94. · Zbl 1009.68053
[105] Thilo Mie. Polylogarithmic two-round argument systems. Journal of Mathematical Cryptology, 2(4):343-363, 2008. · Zbl 1158.94003 · doi:10.1515/JMC.2008.016
[106] Daniele Micciancio and Oded Regev. Worst-case to average-case reductions based on gaussian measures. SIAM Journal on Computing, 37:267-302, April 2007. · Zbl 1142.68037 · doi:10.1137/S0097539705447360
[107] M. Naor, On cryptographic assumptions and challenges, in Proceedings of the 23rd annual international cryptology conference, 2003, pp. 96-109 · Zbl 1122.94391
[108] V.I. Nechaev, Complexity of a determinate algorithm for the discrete logarithm. Mathematical Notes, 55, (1994), pp. 165-172 · Zbl 0831.11065
[109] 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-599 · Zbl 1323.68317
[110] Eiji Okamoto and Kazue Tanaka. Key distribution system based on identification information. Selected Areas in Communications, IEEE Journal on, 7(4):481-485, May 1989. · doi:10.1109/49.17711
[111] R. Pass, Limits of provable security from standard assumptions, in STOC, 2011, pp. 109-118 · Zbl 1288.94080
[112] 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 ’13, 2013, pp. 238-252
[113] O. Paneth, G.N. Rothblum. Publicly verifiable non-interactive arguments for delegating computation. Cryptology ePrint Archive, Report 2014/981, 2014 · Zbl 0940.68048
[114] C. Papamanthou, E. Shi, R. Tamassia, K. Yi, Streaming authenticated data structures, in Proceedings of the international conference on the theory and application of cryptographic techniques, 2013, pp. 353-370 · Zbl 1306.94106
[115] C. Papamanthou, R. Tamassia, N. Triandopoulos, Optimal verification of operations on dynamic sets, in Proceeding of the 31st annual cryptology conference, 2011, pp. 91-110 · Zbl 1287.94094
[116] M. Prabhakaran, R. Xue. Statistically hiding sets, in Proceedings of the cryptographers’ track at the RSA conference 2009, 2009, pp. 100-116 · Zbl 1237.94088
[117] O. Regev, New lattice based cryptographic constructions, in Proceedings of the 35th annual ACM symposium on theory of computing, 2003, pp. 407-416 · Zbl 1192.94105
[118] Oded Regev. New lattice-based cryptographic constructions. Journal of the ACM, 51(6):899-942, 2004. · Zbl 1125.94026 · doi:10.1145/1039488.1039490
[119] 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-93 · Zbl 1192.94106
[120] Alexander A. Razborov and Steven Rudich. Natural proofs. Journal of Computer and System Sciences, 55:204-213, 1994. · Zbl 1345.68165
[121] 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-85 · Zbl 0653.68037
[122] Adi Shamir. IP = PSPACE. Journal of the ACM, 39(4):869-877, 1992. · Zbl 0799.68096 · doi:10.1145/146585.146609
[123] 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-266 · Zbl 1142.68037
[124] 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-18 · Zbl 1162.68448
[125] H. Wee, On round-efficient argument systems, in Proceedings of the 32nd international colloquium on automata, languages and programming, 2005, pp. 140-152 · Zbl 1082.68574
[126] 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 ’15, 2015
[127] 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 ’14, 2014, pp. 856-867
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.