{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,2]],"date-time":"2026-01-02T07:33:30Z","timestamp":1767339210891,"version":"3.41.0"},"publisher-location":"Cham","reference-count":57,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319705026"},{"type":"electronic","value":"9783319705033"}],"license":[{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2017,1,1]],"date-time":"2017-01-01T00:00:00Z","timestamp":1483228800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2017]]},"DOI":"10.1007\/978-3-319-70503-3_6","type":"book-chapter","created":{"date-parts":[[2017,11,4]],"date-time":"2017-11-04T02:43:27Z","timestamp":1509763407000},"page":"172-206","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":19,"title":["Zero Knowledge Protocols from Succinct Constraint Detection"],"prefix":"10.1007","author":[{"given":"Eli","family":"Ben-Sasson","sequence":"first","affiliation":[]},{"given":"Alessandro","family":"Chiesa","sequence":"additional","affiliation":[]},{"given":"Michael A.","family":"Forbes","sequence":"additional","affiliation":[]},{"given":"Ariel","family":"Gabizon","sequence":"additional","affiliation":[]},{"given":"Michael","family":"Riabzev","sequence":"additional","affiliation":[]},{"given":"Nicholas","family":"Spooner","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,5]]},"reference":[{"issue":"3","key":"6_CR1","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1145\/278298.278306","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Lund, C., Motwani, R., Sudan, M., Szegedy, M.: Proof verification, the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998). Preliminary version in FOCS 1992","journal-title":"J. ACM"},{"key":"6_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"449","DOI":"10.1007\/978-3-662-53015-3_16","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"B Applebaum","year":"2016","unstructured":"Applebaum, B., Raykov, P.: On the relationship between statistical zero-knowledge and statistical randomized encodings. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 449\u2013477. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53015-3_16"},{"issue":"1","key":"6_CR3","doi-asserted-by":"publisher","first-page":"70","DOI":"10.1145\/273865.273901","volume":"45","author":"S Arora","year":"1998","unstructured":"Arora, S., Safra, S.: Probabilistic checking of proofs: a new characterization of NP. J. ACM 45(1), 70\u2013122 (1998). Preliminary version in FOCS 1992","journal-title":"J. ACM"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. In: Proceedings of the 17th Annual ACM Symposium on Theory of Computing, STOC 1985, pp. 421\u2013429 (1985)","DOI":"10.1145\/22145.22192"},{"key":"6_CR5","unstructured":"Ben-Sasson, E., Chiesa, A., Gabizon, A., Riabzev, M., Spooner, N.: Interactive oracle proofs with constant rate and query complexity. In: Proceedings of the 44th International Colloquium on Automata, Languages and Programming, ICALP 2017, pp. 40:1\u201340:15 (2017)"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"33","DOI":"10.1007\/978-3-662-49099-0_2","volume-title":"Theory of Cryptography","author":"E Ben-Sasson","year":"2016","unstructured":"Ben-Sasson, E., Chiesa, A., Gabizon, A., Virza, M.: Quasi-linear size zero knowledge from linear-algebraic PCPs. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 33\u201364. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49099-0_2"},{"key":"6_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"31","DOI":"10.1007\/978-3-662-53644-5_2","volume-title":"Theory of Cryptography","author":"E Ben-Sasson","year":"2016","unstructured":"Ben-Sasson, E., Chiesa, A., Spooner, N.: Interactive oracle proofs. In: Hirt, M., Smith, A. (eds.) TCC 2016. LNCS, vol. 9986, pp. 31\u201360. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53644-5_2"},{"key":"6_CR8","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF01200056","volume":"1","author":"L Babai","year":"1991","unstructured":"Babai, L., Fortnow, L., Lund, C.: Non-deterministic exponential time has two-prover interactive protocols. Comput. Complexity 1, 3\u201340 (1991). Preliminary version appeared in FOCS 1990","journal-title":"Comput. Complexity"},{"key":"6_CR9","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: Proceedings of the 23rd Annual ACM Symposium on Theory of Computing, STOC 1991, pp. 21\u201332 (1991)","DOI":"10.1145\/103418.103428"},{"key":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/0-387-34799-2_4","volume-title":"Advances in Cryptology \u2014 CRYPTO 1988","author":"M Ben-Or","year":"1990","unstructured":"Ben-Or, M., Goldreich, O., Goldwasser, S., H\u00e5stad, J., Kilian, J., Micali, S., Rogaway, P.: Everything provable is provable in zero-knowledge. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 37\u201356. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34799-2_4"},{"issue":"4","key":"6_CR11","doi-asserted-by":"publisher","first-page":"889","DOI":"10.1137\/S0097539705446810","volume":"36","author":"E Ben-Sasson","year":"2006","unstructured":"Ben-Sasson, E., Goldreich, O., Harsha, P., Sudan, M., Vadhan, S.P.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. 36(4), 889\u2013974 (2006)","journal-title":"SIAM J. Comput."},{"issue":"7","key":"6_CR12","doi-asserted-by":"publisher","first-page":"3230","DOI":"10.1137\/090779875","volume":"39","author":"E Ben-Sasson","year":"2010","unstructured":"Ben-Sasson, E., Guruswami, V., Kaufman, T., Sudan, M., Viderman, M.: Locally testable codes require redundant testers. SIAM J. Comput. 39(7), 3230\u20133247 (2010)","journal-title":"SIAM J. Comput."},{"key":"6_CR13","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: how to remove intractability assumptions. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988, pp. 113\u2013131 (1988)","DOI":"10.1145\/62212.62223"},{"key":"6_CR14","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for non-cryptographic fault-tolerant distributed computation. In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, STOC 1988, pp. 1\u201310 (1988)","DOI":"10.1145\/62212.62213"},{"issue":"1","key":"6_CR15","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1137\/S0097539704445445","volume":"35","author":"E Ben-Sasson","year":"2005","unstructured":"Ben-Sasson, E., Harsha, P., Raskhodnikova, S.: Some 3CNF properties are hard to test. SIAM J. Comput. 35(1), 1\u201321 (2005)","journal-title":"SIAM J. Comput."},{"issue":"2","key":"6_CR16","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1016\/0020-0190(87)90232-8","volume":"25","author":"RB Boppana","year":"1987","unstructured":"Boppana, R.B., H\u00e5stad, J., Zachos, S.: Does co-NP have short interactive proofs? Inf. Process. Lett. 25(2), 127\u2013132 (1987)","journal-title":"Inf. Process. Lett."},{"issue":"2","key":"6_CR17","doi-asserted-by":"publisher","first-page":"254","DOI":"10.1016\/0022-0000(88)90028-1","volume":"36","author":"L Babai","year":"1988","unstructured":"Babai, L., Moran, S.: Arthur-merlin games: a randomized proof system, and a hierarchy of complexity classes. J. Comput. Syst. Sci. 36(2), 254\u2013276 (1988)","journal-title":"J. Comput. Syst. Sci."},{"issue":"2","key":"6_CR18","doi-asserted-by":"publisher","first-page":"551","DOI":"10.1137\/050646445","volume":"38","author":"E Ben-Sasson","year":"2008","unstructured":"Ben-Sasson, E., Sudan, M.: Short PCPs with polylog query complexity. SIAM J. Comput. 38(2), 551\u2013607 (2008). Preliminary version appeared in STOC 2005","journal-title":"SIAM J. Comput."},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/978-3-540-27821-4_27","volume-title":"Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques","author":"A Bogdanov","year":"2004","unstructured":"Bogdanov, A., Wee, H.: A stateful implementation of a random function supporting parity queries over hypercubes. In: Jansen, K., Khanna, S., Rolim, J.D.P., Ron, D. (eds.) APPROX\/RANDOM -2004. LNCS, vol. 3122, pp. 298\u2013309. Springer, Heidelberg (2004). https:\/\/doi.org\/10.1007\/978-3-540-27821-4_27"},{"key":"6_CR20","unstructured":"Chiesa, A., Forbes, M.A., Spooner, N.: A zero knowledge sumcheck and its applications. Cryptology ePrint Archive, Report 2017\/305 (2017)"},{"key":"6_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"215","DOI":"10.1007\/3-540-48071-4_15","volume-title":"Advances in Cryptology \u2014 CRYPTO 1992","author":"C Dwork","year":"1993","unstructured":"Dwork, C., Feige, U., Kilian, J., Naor, M., Safra, M.: Low communication 2-prover zero-knowledge proofs for NP. In: Brickell, E.F. (ed.) CRYPTO 1992. LNCS, vol. 740, pp. 215\u2013227. Springer, Heidelberg (1993). https:\/\/doi.org\/10.1007\/3-540-48071-4_15"},{"key":"6_CR22","doi-asserted-by":"crossref","unstructured":"Dinur, I., Reingold, O.: Assignment testers: towards a combinatorial proof of the PCP theorem. In: Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2004, pp. 155\u2013164 (2004)","DOI":"10.1109\/FOCS.2004.16"},{"key":"6_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"442","DOI":"10.1007\/BFb0055746","volume-title":"Advances in Cryptology \u2014 CRYPTO \u201998","author":"C Dwork","year":"1998","unstructured":"Dwork, C., Sahai, A.: Concurrent zero-knowledge: reducing the need for timing constraints. In: Krawczyk, H. (ed.) CRYPTO 1998. LNCS, vol. 1462, pp. 442\u2013457. Springer, Heidelberg (1998). https:\/\/doi.org\/10.1007\/BFb0055746"},{"issue":"2","key":"6_CR24","doi-asserted-by":"publisher","first-page":"268","DOI":"10.1145\/226643.226652","volume":"43","author":"U Feige","year":"1996","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Interactive proofs, the hardness of approximating cliques. J. ACM 43(2), 268\u2013292 (1996). Preliminary version in FOCS 1991","journal-title":"J. ACM"},{"key":"6_CR25","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Rompel, J., Sipser, M.: On the power of multi-prover interactive protocols. In: Theoretical Computer Science, pp. 156\u2013161 (1988)","DOI":"10.1109\/SCT.1988.5275"},{"key":"6_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"526","DOI":"10.1007\/0-387-34805-0_46","volume-title":"Advances in Cryptology \u2014 CRYPTO 1989 Proceedings","author":"U Feige","year":"1990","unstructured":"Feige, U., Shamir, A.: Zero knowledge proofs of knowledge in two rounds. In: Brassard, G. (ed.) CRYPTO 1989. LNCS, vol. 435, pp. 526\u2013544. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34805-0_46"},{"issue":"7","key":"6_CR27","doi-asserted-by":"publisher","first-page":"2761","DOI":"10.1137\/080722771","volume":"39","author":"O Goldreich","year":"2010","unstructured":"Goldreich, O., Goldwasser, S., Nussboim, A.: On the implementation of huge random objects. SIAM J. Comput. 39(7), 2761\u20132822 (2010). Preliminary version appeared in FOCS 2003","journal-title":"SIAM J. Comput."},{"key":"6_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1007\/978-3-642-14623-7_10","volume-title":"Advances in Cryptology \u2013 CRYPTO 2010","author":"V Goyal","year":"2010","unstructured":"Goyal, V., Ishai, Y., Mahmoody, M., Sahai, A.: Interactive locking, zero-knowledge PCPs, and unconditional cryptography. In: Rabin, T. (ed.) CRYPTO 2010. LNCS, vol. 6223, pp. 173\u2013190. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14623-7_10"},{"key":"6_CR29","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for Muggles. In: Proceedings of the 40th Annual ACM Symposium on Theory of Computing, STOC 2008, pp. 113\u2013122 (2008)","DOI":"10.1145\/1374376.1374396"},{"issue":"1","key":"6_CR30","doi-asserted-by":"publisher","first-page":"186","DOI":"10.1137\/0218012","volume":"18","author":"S Goldwasser","year":"1989","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186\u2013208 (1989). Preliminary version appeared in STOC 1985","journal-title":"SIAM J. Comput."},{"issue":"3","key":"6_CR31","doi-asserted-by":"publisher","first-page":"691","DOI":"10.1145\/116825.116852","volume":"38","author":"O Goldreich","year":"1991","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691\u2013729 (1991). Preliminary version appeared in FOCS 1986","journal-title":"J. ACM"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Vadhan, S.P.: Comparing entropies in statistical zero knowledge with applications to the structure of SZK. In: Proceedings of the 14th Annual IEEE Conference on Computational Complexity, CCC 1999, p. 54 (1999)","DOI":"10.1109\/CCC.1999.766262"},{"key":"6_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"151","DOI":"10.1007\/978-3-642-28914-9_9","volume-title":"Theory of Cryptography","author":"Y Ishai","year":"2012","unstructured":"Ishai, Y., Mahmoody, M., Sahai, A.: On efficient zero-knowledge PCPs. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 151\u2013168. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28914-9_9"},{"key":"6_CR34","unstructured":"Ishai, Y., Mahmoody, M., Sahai, A., Xiao, D.: On zero-knowledge PCPs: limitations, simplifications, and applications (2015). http:\/\/www.cs.virginia.edu\/~mohammad\/files\/papers\/ZKPCPs-Full.pdf"},{"issue":"1","key":"6_CR35","doi-asserted-by":"publisher","first-page":"37","DOI":"10.1007\/s001459900018","volume":"10","author":"T Itoh","year":"1997","unstructured":"Itoh, T., Ohta, Y., Shizuya, H.: A language-dependent cryptographic primitive. J. Cryptol. 10(1), 37\u201350 (1997)","journal-title":"J. Cryptol."},{"key":"6_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"121","DOI":"10.1007\/978-3-642-54242-8_6","volume-title":"Theory of Cryptography","author":"Y Ishai","year":"2014","unstructured":"Ishai, Y., Weiss, M.: Probabilistically checkable proofs of proximity with zero-knowledge. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 121\u2013145. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_6"},{"key":"6_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/978-3-662-49099-0_1","volume-title":"Theory of Cryptography","author":"Y Ishai","year":"2016","unstructured":"Ishai, Y., Weiss, M., Yang, G.: Making the best of a leaky situation: zero-knowledge PCPs from leakage-resilient circuits. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9563, pp. 3\u201332. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49099-0_1"},{"key":"6_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"40","DOI":"10.1007\/3-540-48184-2_4","volume-title":"Advances in Cryptology \u2014 CRYPTO 1987","author":"R Impagliazzo","year":"1988","unstructured":"Impagliazzo, R., Yung, M.: Direct minimum-knowledge computations (extended abstract). In: Pomerance, C. (ed.) CRYPTO 1987. LNCS, vol. 293, pp. 40\u201351. Springer, Heidelberg (1988). https:\/\/doi.org\/10.1007\/3-540-48184-2_4"},{"key":"6_CR39","unstructured":"Kayal, N.: Algorithms for arithmetic circuits (2010). ECCC TR10-073"},{"issue":"1\u20132","key":"6_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-004-0182-6","volume":"13","author":"V Kabanets","year":"2004","unstructured":"Kabanets, V., Impagliazzo, R.: Derandomizing polynomial identity tests means proving circuit lower bounds. Comput. Complexity 13(1\u20132), 1\u201346 (2004)","journal-title":"Comput. Complexity"},{"key":"6_CR41","doi-asserted-by":"crossref","unstructured":"Kilian, J., Petrank, E., Tardos, G.: Probabilistically checkable proofs with zero knowledge. In: Proceedings of the 29th Annual ACM Symposium on Theory of Computing, STOC 1997, pp. 496\u2013505 (1997)","DOI":"10.1145\/258533.258643"},{"key":"6_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"536","DOI":"10.1007\/978-3-540-70583-3_44","volume-title":"Automata, Languages and Programming","author":"YT Kalai","year":"2008","unstructured":"Kalai, Y.T., Raz, R.: Interactive PCP. In: Aceto, L., Damg\u00e5rd, I., Goldberg, L.A., Halld\u00f3rsson, M.M., Ing\u00f3lfsd\u00f3ttir, A., Walukiewicz, I. (eds.) ICALP 2008. LNCS, vol. 5126, pp. 536\u2013547. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-70583-3_44"},{"issue":"4","key":"6_CR43","doi-asserted-by":"publisher","first-page":"859","DOI":"10.1145\/146585.146605","volume":"39","author":"C Lund","year":"1992","unstructured":"Lund, C., Fortnow, L., Karloff, H.J., Nisan, N.: Algebraic methods for interactive proof systems. J. ACM 39(4), 859\u2013868 (1992)","journal-title":"J. ACM"},{"issue":"2","key":"6_CR44","doi-asserted-by":"publisher","first-page":"204","DOI":"10.1007\/BF01200756","volume":"15","author":"D Lapidot","year":"1995","unstructured":"Lapidot, D., Shamir, A.: A one-round, two-prover, zero-knowledge protocol for NP. Combinatorica 15(2), 204\u2013214 (1995)","journal-title":"Combinatorica"},{"issue":"1","key":"6_CR45","doi-asserted-by":"publisher","first-page":"47","DOI":"10.1006\/jcss.1999.1664","volume":"60","author":"T Okamoto","year":"2000","unstructured":"Okamoto, T.: On relationships between statistical zero-knowledge proofs. J. Comput. Syst. Sci. 60(1), 47\u2013108 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"6_CR46","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R.: One-way functions, hard on average problems, and statistical zero-knowledge proofs. In: Proceedings of the 6th Annual Structure in Complexity Theory Conference, CoCo 1991, pp. 133\u2013138 (1991)","DOI":"10.1109\/SCT.1991.160253"},{"key":"6_CR47","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"482","DOI":"10.1007\/978-3-540-78524-8_27","volume-title":"Theory of Cryptography","author":"SJ Ong","year":"2008","unstructured":"Ong, S.J., Vadhan, S.: An equivalence between zero knowledge and commitments. In: Canetti, R. (ed.) TCC 2008. LNCS, vol. 4948, pp. 482\u2013500. Springer, Heidelberg (2008). https:\/\/doi.org\/10.1007\/978-3-540-78524-8_27"},{"key":"6_CR48","unstructured":"Ostrovsky, R., Wigderson, A.: One-way functions are essential for non-trivial zero-knowledge. In: Proceedings of the 2nd Israel Symposium on Theory of Computing Systems, ISTCS 1993, pp. 3\u201317 (1993)"},{"key":"6_CR49","doi-asserted-by":"crossref","unstructured":"Reingold, O., Rothblum, R., Rothblum, G.: Constant-round interactive proofs for delegating computation. In: Proceedings of the 48th ACM Symposium on the Theory of Computing, STOC 2016, pp. 49\u201362 (2016)","DOI":"10.1145\/2897518.2897652"},{"issue":"1","key":"6_CR50","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/s00037-005-0188-8","volume":"14","author":"R Raz","year":"2005","unstructured":"Raz, R., Shpilka, A.: Deterministic polynomial identity testing in non-commutative models. Comput. Complexity 14(1), 1\u201319 (2005). Preliminary version appeared in CCC 2004","journal-title":"Comput. Complexity"},{"issue":"4","key":"6_CR51","doi-asserted-by":"publisher","first-page":"701","DOI":"10.1145\/322217.322225","volume":"27","author":"JT Schwartz","year":"1980","unstructured":"Schwartz, J.T.: Fast probabilistic algorithms for verification of polynomial identities. J. ACM 27(4), 701\u2013717 (1980)","journal-title":"J. ACM"},{"issue":"4","key":"6_CR52","doi-asserted-by":"publisher","first-page":"869","DOI":"10.1145\/146585.146609","volume":"39","author":"A Shamir","year":"1992","unstructured":"Shamir, A.: IP = PSPACE. J. ACM 39(4), 869\u2013877 (1992)","journal-title":"J. ACM"},{"issue":"2","key":"6_CR53","doi-asserted-by":"publisher","first-page":"196","DOI":"10.1145\/636865.636868","volume":"50","author":"A Sahai","year":"2003","unstructured":"Sahai, A., Vadhan, S.P.: A complete problem for statistical zero knowledge. J. ACM 50(2), 196\u2013249 (2003)","journal-title":"J. ACM"},{"issue":"3\u20134","key":"6_CR54","first-page":"207","volume":"5","author":"A Shpilka","year":"2010","unstructured":"Shpilka, A., Yehudayoff, A.: Arithmetic circuits: a survey of recent results and open questions. Found. Trends Theoret. Comput. Sci. 5(3\u20134), 207\u2013388 (2010)","journal-title":"Found. Trends Theoret. Comput. Sci."},{"key":"6_CR55","unstructured":"Vadhan, S.P.: A Study of statistical zero-knowledge proofs. Ph.D. thesis, MIT, August 1999"},{"key":"6_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1007\/978-3-662-48797-6_27","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2015","author":"V Vaikuntanathan","year":"2015","unstructured":"Vaikuntanathan, V., Vasudevan, P.N.: Secret sharing and statistical zero knowledge. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 656\u2013680. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48797-6_27"},{"key":"6_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"216","DOI":"10.1007\/3-540-09519-5_73","volume-title":"Symbolic and Algebraic Computation","author":"R Zippel","year":"1979","unstructured":"Zippel, R.: Probabilistic algorithms for sparse polynomials. In: Ng, E.W. (ed.) Symbolic and Algebraic Computation. LNCS, vol. 72, pp. 216\u2013226. Springer, Heidelberg (1979). https:\/\/doi.org\/10.1007\/3-540-09519-5_73"}],"container-title":["Lecture Notes in Computer Science","Theory of Cryptography"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-70503-3_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,26]],"date-time":"2025-06-26T21:25:35Z","timestamp":1750973135000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-70503-3_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319705026","9783319705033"],"references-count":57,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-70503-3_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2017]]},"assertion":[{"value":"5 November 2017","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"TCC","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Theory of Cryptography Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Baltimore","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"USA","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2017","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"12 November 2017","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 November 2017","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2017","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"http:\/\/www.iacr.org\/workshops\/tcc2017\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}