{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,21]],"date-time":"2026-03-21T19:26:33Z","timestamp":1774121193255,"version":"3.50.1"},"publisher-location":"Cham","reference-count":86,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783030269531","type":"print"},{"value":"9783030269548","type":"electronic"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"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":[],"published-print":{"date-parts":[[2019]]},"DOI":"10.1007\/978-3-030-26954-8_3","type":"book-chapter","created":{"date-parts":[[2019,8,8]],"date-time":"2019-08-08T23:02:47Z","timestamp":1565305367000},"page":"67-97","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":97,"title":["Zero-Knowledge Proofs on Secret-Shared Data via Fully Linear PCPs"],"prefix":"10.1007","author":[{"given":"Dan","family":"Boneh","sequence":"first","affiliation":[]},{"given":"Elette","family":"Boyle","sequence":"additional","affiliation":[]},{"given":"Henry","family":"Corrigan-Gibbs","sequence":"additional","affiliation":[]},{"given":"Niv","family":"Gilboa","sequence":"additional","affiliation":[]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2019,8,1]]},"reference":[{"issue":"1","key":"3_CR1","first-page":"2","volume":"1","author":"S Aaronson","year":"2009","unstructured":"Aaronson, S., Wigderson, A.: Algebrization: a new barrier in complexity theory. ACM Trans. Comput. Theory (TOCT) 1(1), 2 (2009)","journal-title":"ACM Trans. Comput. Theory (TOCT)"},{"key":"3_CR2","doi-asserted-by":"crossref","unstructured":"Ames, S., Hazay, C., Ishai, Y., Venkitasubramaniam, M.: Ligero: lightweight sublinear arguments without a trusted setup. In: CCS (2017)","DOI":"10.1145\/3133956.3134104"},{"key":"3_CR3","unstructured":"Andrew, C.C.Y.: Some complexity questions related to distributed computing. In: STOC (1979)"},{"key":"3_CR4","doi-asserted-by":"crossref","unstructured":"Araki, T., et al.: Optimized honest-majority MPC for malicious adversaries - breaking the 1 billion-gate per second barrier. In: IEEE Symposium on Security and Privacy (2017)","DOI":"10.1109\/SP.2017.15"},{"key":"3_CR5","doi-asserted-by":"crossref","unstructured":"Araki, T., Furukawa, J., Lindell, Y., Nof, A., Ohara, K.: High-throughput semi-honest secure three-party computation with an honest majority. In: ACM CCS (2016)","DOI":"10.1145\/2976749.2978331"},{"issue":"3","key":"3_CR6","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 and the hardness of approximation problems. J. ACM 45(3), 501\u2013555 (1998)","journal-title":"J. ACM"},{"issue":"1","key":"3_CR7","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)","journal-title":"J. ACM"},{"key":"3_CR8","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. In: STOC (1985)","DOI":"10.1145\/22145.22192"},{"key":"3_CR9","doi-asserted-by":"crossref","unstructured":"Babai, L., Fortnow, L., Levin, L.A., Szegedy, M.: Checking computations in polylogarithmic time. In: STOC (1991)","DOI":"10.1145\/103418.103428"},{"issue":"2","key":"3_CR10","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."},{"key":"3_CR11","doi-asserted-by":"crossref","unstructured":"Backes, M., Barbosa, M., Fiore, D., Reischuk, R.M.: ADSNARK: nearly practical and privacy-preserving proofs on authenticated data. In: 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, 17\u201321 May 2015 (2015)","DOI":"10.1109\/SP.2015.24"},{"key":"3_CR12","doi-asserted-by":"crossref","unstructured":"Bellare, M., Rogaway, P.: Random oracles are practical: a paradigm for designing efficient protocols. In: CCS (1993)","DOI":"10.1145\/168588.168596"},{"key":"3_CR13","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., et al.: 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"},{"key":"3_CR14","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Kilian, J., Wigderson, A.: Multi-prover interactive proofs: how to remove intractability assumptions. In: STOC (1988)","DOI":"10.1145\/62212.62223"},{"key":"3_CR15","unstructured":"Ben-Sasson, E., Bentov, I., Horesh, Y., Riabzev, M.: Scalable, transparent, and post-quantum secure computational integrity. Cryptology ePrint Archive, Report 2018\/046 (2018)"},{"key":"3_CR16","unstructured":"Ben-Sasson, E., Chiesa, A., Forbes, M.A., Gabizon, A., Riabzev, M., Spooner, N.: On probabilistic checking in perfect zero knowledge. In: Electronic Colloquium on Computational Complexity (ECCC), no. 156 (2016)"},{"key":"3_CR17","doi-asserted-by":"crossref","unstructured":"Ben-Sasson, E., Chiesa, A., Gabizon, A., Riabzev, M., Spooner, N.: Interactive oracle proofs with constant rate and query complexity. In: ICALP (2017)","DOI":"10.1007\/978-3-662-53644-5_2"},{"key":"3_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-40084-1_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"E Ben-Sasson","year":"2013","unstructured":"Ben-Sasson, E., Chiesa, A., Genkin, D., Tromer, E., Virza, M.: SNARKs for C: verifying program executions succinctly and in zero knowledge. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 90\u2013108. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40084-1_6"},{"key":"3_CR19","unstructured":"Ben-Sasson, E., Chiesa, A., Riabzev, M., Spooner, N., Virza, M., Ward, N.P.: Aurora: transparent succinct arguments for R1CS. Cryptology ePrint Archive, Report 2018\/828 (2018). https:\/\/eprint.iacr.org\/2018\/828"},{"key":"3_CR20","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"},{"issue":"4","key":"3_CR21","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.: Robust PCPs of proximity, shorter PCPs, and applications to coding. SIAM J. Comput. 36(4), 889\u2013974 (2006)","journal-title":"SIAM J. Comput."},{"key":"3_CR22","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Canetti, R., Chiesa, A., Tromer, E.: From extractable collision resistance to succinct non-interactive arguments of knowledge, and back again. In: Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, 8\u201310 January 2012 (2012)","DOI":"10.1145\/2090236.2090263"},{"key":"3_CR23","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"315","DOI":"10.1007\/978-3-642-36594-2_18","volume-title":"Theory of Cryptography","author":"N Bitansky","year":"2013","unstructured":"Bitansky, N., Chiesa, A., Ishai, Y., Paneth, O., Ostrovsky, R.: Succinct non-interactive arguments via linear interactive proofs. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 315\u2013333. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36594-2_18"},{"key":"3_CR24","doi-asserted-by":"crossref","unstructured":"Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications (extended abstract). In: Proceedings of the 20th Annual ACM Symposium on Theory of Computing, Chicago, Illinois, USA, 2\u20134 May 1988 (1988)","DOI":"10.1145\/62212.62222"},{"key":"3_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"247","DOI":"10.1007\/978-3-319-56617-7_9","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"D Boneh","year":"2017","unstructured":"Boneh, D., Ishai, Y., Sahai, A., Wu, D.J.: Lattice-based SNARGs and their application to more efficient obfuscation. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10212, pp. 247\u2013277. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56617-7_9"},{"key":"3_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"222","DOI":"10.1007\/978-3-319-78372-7_8","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"D Boneh","year":"2018","unstructured":"Boneh, D., Ishai, Y., Sahai, A., Wu, D.J.: Quasi-optimal SNARGs via linear multi-prover interactive proofs. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 222\u2013255. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78372-7_8"},{"key":"3_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/978-3-662-49896-5_12","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"J Bootle","year":"2016","unstructured":"Bootle, J., Cerulli, A., Chaidos, P., Groth, J., Petit, C.: Efficient zero-knowledge arguments for arithmetic circuits in the discrete log setting. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 327\u2013357. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_12"},{"key":"3_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1007\/978-3-319-70700-6_12","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2017","author":"J Bootle","year":"2017","unstructured":"Bootle, J., Cerulli, A., Ghadafi, E., Groth, J., Hajiabadi, M., Jakobsen, S.K.: Linear-time zero-knowledge proofs for arithmetic circuit satisfiability. In: Takagi, T., Peyrin, T. (eds.) ASIACRYPT 2017. LNCS, vol. 10626, pp. 336\u2013365. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70700-6_12"},{"key":"3_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"561","DOI":"10.1007\/978-3-319-76581-5_19","volume-title":"Public-Key Cryptography \u2013 PKC 2018","author":"J Bootle","year":"2018","unstructured":"Bootle, J., Groth, J.: Efficient batch zero-knowledge arguments for low degree polynomials. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10770, pp. 561\u2013588. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-76581-5_19"},{"key":"3_CR30","doi-asserted-by":"crossref","unstructured":"Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing: improvements and extensions. In: CCS (2016)","DOI":"10.1145\/2976749.2978429"},{"key":"3_CR31","doi-asserted-by":"crossref","unstructured":"B\u00fcnz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: efficient range proofs for confidential transactions. Cryptology ePrint Archive, Report 2017\/1066 (2017)","DOI":"10.1109\/SP.2018.00020"},{"key":"3_CR32","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1007\/978-3-642-36362-7_5","volume-title":"Public-Key Cryptography \u2013 PKC 2013","author":"D Catalano","year":"2013","unstructured":"Catalano, D., Fiore, D.: Vector commitments and their applications. In: Kurosawa, K., Hanaoka, G. (eds.) PKC 2013. LNCS, vol. 7778, pp. 55\u201372. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36362-7_5"},{"issue":"1","key":"3_CR33","doi-asserted-by":"publisher","first-page":"7","DOI":"10.1145\/2636924","volume":"11","author":"A Chakrabarti","year":"2014","unstructured":"Chakrabarti, A., Cormode, G., McGregor, A., Thaler, J.: Annotations in data streams. ACM Trans. Algorithms 11(1), 7 (2014)","journal-title":"ACM Trans. Algorithms"},{"key":"3_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"34","DOI":"10.1007\/978-3-319-96878-0_2","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"K Chida","year":"2018","unstructured":"Chida, K., et al.: Fast large-scale honest-majority MPC for malicious adversaries. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10993, pp. 34\u201364. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96878-0_2"},{"key":"3_CR35","doi-asserted-by":"crossref","unstructured":"Cormode, G., Mitzenmacher, M., Thaler, J.: Practical verified computation with streaming interactive proofs. In: ITCS (2012)","DOI":"10.1145\/2090236.2090245"},{"issue":"1","key":"3_CR36","doi-asserted-by":"publisher","first-page":"25","DOI":"10.14778\/2047485.2047488","volume":"5","author":"G Cormode","year":"2011","unstructured":"Cormode, G., Thaler, J., Yi, K.: Verifying computations with streaming interactive proofs. Proc. VLDB Endow. 5(1), 25\u201336 (2011)","journal-title":"Proc. VLDB Endow."},{"key":"3_CR37","unstructured":"Corrigan-Gibbs, H., Boneh, D.: Prio: private, robust, and scalable computation of aggregate statistics. In: NSDI (2017)"},{"key":"3_CR38","doi-asserted-by":"crossref","unstructured":"Corrigan-Gibbs, H., Boneh, D., Mazi\u00e8res, D.: Riposte: an anonymous messaging system handling millions of users. In: Symposium on Security and Privacy (2015)","DOI":"10.1109\/SP.2015.27"},{"key":"3_CR39","doi-asserted-by":"crossref","unstructured":"Costello, C., et al.: Geppetto: versatile verifiable computation. In: 2015 IEEE Symposium on Security and Privacy, SP 2015, San Jose, CA, USA, 17\u201321 May 2015 (2015)","DOI":"10.1109\/SP.2015.23"},{"key":"3_CR40","unstructured":"Couteau, G.: A note on the communication complexity of multiparty computation in the correlated randomness model. IACR Cryptology ePrint Archive 2018, 465 (2018)"},{"key":"3_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"530","DOI":"10.1007\/978-3-319-76581-5_18","volume-title":"Public-Key Cryptography \u2013 PKC 2018","author":"I Damg\u00e5rd","year":"2018","unstructured":"Damg\u00e5rd, I., Luo, J., Oechsner, S., Scholl, P., Simkin, M.: Compact zero-knowledge proofs of small hamming weight. In: Abdalla, M., Dahab, R. (eds.) PKC 2018. LNCS, vol. 10770, pp. 530\u2013560. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-76581-5_18"},{"key":"3_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"572","DOI":"10.1007\/978-3-540-74143-5_32","volume-title":"Advances in Cryptology - CRYPTO 2007","author":"I Damg\u00e5rd","year":"2007","unstructured":"Damg\u00e5rd, I., Nielsen, J.B.: Scalable and unconditionally secure multiparty computation. In: Menezes, A. (ed.) CRYPTO 2007. LNCS, vol. 4622, pp. 572\u2013590. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-74143-5_32"},{"key":"3_CR43","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"167","DOI":"10.1007\/978-3-319-63688-7_6","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"I Damg\u00e5rd","year":"2017","unstructured":"Damg\u00e5rd, I., Nielsen, J.B., Nielsen, M., Ranellucci, S.: The tinytable protocol for 2-party secure computation, or: gate-scrambling revisited. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 167\u2013187. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_6"},{"key":"3_CR44","unstructured":"Eerikson, H., Orlandi, C., Pullonen, P., Puura, J., Simkin, M.: Use your brain! Arithmetic 3PC for any modulus with active security. IACR Cryptology ePrint Archive 2019, 164 (2019)"},{"key":"3_CR45","unstructured":"Feige, U., Goldwasser, S., Lov\u00e1sz, L., Safra, S., Szegedy, M.: Approximating clique is almost NP-complete. In: FOCS (1991)"},{"issue":"2","key":"3_CR46","doi-asserted-by":"publisher","first-page":"545","DOI":"10.1016\/0304-3975(94)90251-8","volume":"134","author":"L Fortnow","year":"1994","unstructured":"Fortnow, L., Rompel, J., Sipser, M.: On the power of multi-prover interactive protocols. Theor. Comput. Sci. 134(2), 545\u2013557 (1994)","journal-title":"Theor. Comput. Sci."},{"key":"3_CR47","doi-asserted-by":"crossref","unstructured":"Fortnow, L., Santhanam, R.: Infeasibility of instance compression and succinct PCPs for NP. In: STOC (2008)","DOI":"10.1145\/1374376.1374398"},{"key":"3_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"225","DOI":"10.1007\/978-3-319-56614-6_8","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2017","author":"J Furukawa","year":"2017","unstructured":"Furukawa, J., Lindell, Y., Nof, A., Weinstein, O.: High-throughput secure three-party computation for malicious adversaries and an honest majority. In: Coron, J.-S., Nielsen, J.B. (eds.) EUROCRYPT 2017. LNCS, vol. 10211, pp. 225\u2013255. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-56614-6_8"},{"key":"3_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"626","DOI":"10.1007\/978-3-642-38348-9_37","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2013","author":"R Gennaro","year":"2013","unstructured":"Gennaro, R., Gentry, C., Parno, B., Raykova, M.: Quadratic span programs and succinct NIZKs without PCPs. In: Johansson, T., Nguyen, P.Q. (eds.) EUROCRYPT 2013. LNCS, vol. 7881, pp. 626\u2013645. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-38348-9_37"},{"key":"3_CR50","doi-asserted-by":"crossref","unstructured":"Goldreich, O., Micali, S., Wigderson, A.: How to play any mental game or a completeness theorem for protocols with honest majority. In: STOC (1987)","DOI":"10.1145\/28395.28420"},{"key":"3_CR51","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. In: STOC (2008)","DOI":"10.1145\/1374376.1374396"},{"issue":"4","key":"3_CR52","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1145\/2699436","volume":"62","author":"S Goldwasser","year":"2015","unstructured":"Goldwasser, S., Kalai, Y.T., Rothblum, G.N.: Delegating computation: interactive proofs for muggles. J. ACM 62(4), 27 (2015)","journal-title":"J. ACM"},{"issue":"1","key":"3_CR53","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)","journal-title":"SIAM J. Comput."},{"key":"3_CR54","doi-asserted-by":"crossref","unstructured":"Gordon, S.D., Ranellucci, S., Wang, X.: Secure computation with low communication from cross-checking. IACR Cryptology ePrint Archive 2018, 216 (2018)","DOI":"10.1007\/978-3-030-03332-3_3"},{"key":"3_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-642-17373-8_19","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"J Groth","year":"2010","unstructured":"Groth, J.: Short pairing-based non-interactive zero-knowledge arguments. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 321\u2013340. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-17373-8_19"},{"key":"3_CR56","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"305","DOI":"10.1007\/978-3-662-49896-5_11","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"J Groth","year":"2016","unstructured":"Groth, J.: On the size of pairing-based non-interactive arguments. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 305\u2013326. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_11"},{"key":"3_CR57","unstructured":"Gur, T., Rothblum, R.D.: A hierarchy theorem for interactive proofs of proximity. In: 8th Innovations in Theoretical Computer Science Conference, ITCS 2017, Berkeley, CA, USA, 9\u201311 January 2017 (2017)"},{"key":"3_CR58","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R.: Efficient arguments without short PCPs. In: Conference on Computational Complexity (2007)","DOI":"10.1109\/CCC.2007.10"},{"key":"3_CR59","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"},{"key":"3_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"422","DOI":"10.1007\/978-3-662-48000-7_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"YT Kalai","year":"2015","unstructured":"Kalai, Y.T., Rothblum, R.D.: Arguments of proximity. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 422\u2013442. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_21"},{"key":"3_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1007\/978-3-642-17373-8_11","volume-title":"Advances in Cryptology - ASIACRYPT 2010","author":"A Kate","year":"2010","unstructured":"Kate, A., Zaverucha, G.M., Goldberg, I.: Constant-size commitments to polynomials and their applications. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 177\u2013194. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-17373-8_11"},{"key":"3_CR62","doi-asserted-by":"crossref","unstructured":"Katz, J., Kolesnikov, V., Wang, X.: Improved non-interactive zero knowledge with applications to post-quantum signatures. Technical report, Cryptology ePrint Archive, Report 2018\/475 (2018)","DOI":"10.1145\/3243734.3243805"},{"key":"3_CR63","doi-asserted-by":"crossref","unstructured":"Kilian, J.: A note on efficient zero-knowledge proofs and arguments. In: STOC (1992)","DOI":"10.1145\/129712.129782"},{"key":"3_CR64","unstructured":"Klauck, H.: Rectangle size bounds and threshold covers in communication complexity. In: Conference on Computational Complexity (2003)"},{"key":"3_CR65","doi-asserted-by":"crossref","unstructured":"Kol, G., Oshman, R., Saxena, R.R.: Interactive distributed proofs. In: Proceedings of the 2018 ACM Symposium on Principles of Distributed Computing, PODC 2018, Egham, United Kingdom, 23\u201327 July 2018 (2018)","DOI":"10.1145\/3212734.3212771"},{"key":"3_CR66","doi-asserted-by":"publisher","first-page":"331","DOI":"10.1016\/S0065-2458(08)60342-3","volume":"44","author":"E Kushilevitz","year":"1997","unstructured":"Kushilevitz, E.: Communication complexity. Adv. Comput. 44, 331\u2013360 (1997)","journal-title":"Adv. Comput."},{"key":"3_CR67","doi-asserted-by":"crossref","unstructured":"Lindell, Y., Nof, A.: A framework for constructing fast MPC over arithmetic circuits with malicious adversaries and an honest-majority. In: ACM SIGSAC Conference on Computer and Communications Security, CCS (2017)","DOI":"10.1145\/3133956.3133999"},{"key":"3_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1007\/978-3-642-28914-9_10","volume-title":"Theory of Cryptography","author":"H Lipmaa","year":"2012","unstructured":"Lipmaa, H.: Progression-free sets and sublinear pairing-based non-interactive zero-knowledge arguments. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 169\u2013189. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-28914-9_10"},{"key":"3_CR69","unstructured":"Micali, S.: CS proofs. In: FOCS (1994)"},{"key":"3_CR70","doi-asserted-by":"crossref","unstructured":"Mohassel, P., Rosulek, M., Zhang, Y.: Fast and secure three-party computation: the garbled circuit approach. In: ACM SIGSAC Conference on Computer and Communications Security, CCS (2015)","DOI":"10.1145\/2810103.2813705"},{"key":"3_CR71","unstructured":"Naor, M., Parter, M., Yogev, E.: The power of distributed verifiers in interactive proofs. http:\/\/arxiv.org\/abs\/1812.10917 (2018)"},{"key":"3_CR72","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"321","DOI":"10.1007\/978-3-319-93387-0_17","volume-title":"Applied Cryptography and Network Security","author":"PS Nordholt","year":"2018","unstructured":"Nordholt, P.S., Veeningen, M.: Minimising communication in honest-majority MPC by batchwise multiplication verification. In: Preneel, B., Vercauteren, F. (eds.) ACNS 2018. LNCS, vol. 10892, pp. 321\u2013339. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-93387-0_17"},{"key":"3_CR73","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/3-540-48910-X_16","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 1999","author":"P Paillier","year":"1999","unstructured":"Paillier, P.: Public-key cryptosystems based on composite degree residuosity classes. In: Stern, J. (ed.) EUROCRYPT 1999. LNCS, vol. 1592, pp. 223\u2013238. Springer, Heidelberg (1999). https:\/\/doi.org\/10.1007\/3-540-48910-X_16"},{"key":"3_CR74","doi-asserted-by":"crossref","unstructured":"Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. In: Symposium on Security and Privacy (2013)","DOI":"10.1109\/SP.2013.47"},{"issue":"2","key":"3_CR75","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/2856449","volume":"59","author":"B Parno","year":"2016","unstructured":"Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. Commun. ACM 59(2), 103\u2013112 (2016)","journal-title":"Commun. ACM"},{"key":"3_CR76","doi-asserted-by":"crossref","unstructured":"Reingold, O., Rothblum, G.N., Rothblum, R.D.: Constant-round interactive proofs for delegating computation. In: Proceedings of the Forty-Eighth Annual ACM Symposium on Theory of Computing (2016)","DOI":"10.1145\/2897518.2897652"},{"issue":"2","key":"3_CR77","doi-asserted-by":"publisher","first-page":"265","DOI":"10.1007\/s00037-010-0291-3","volume":"19","author":"GN Rothblum","year":"2010","unstructured":"Rothblum, G.N., Vadhan, S.P.: Are PCPs inherent in efficient arguments? Comput. Complex. 19(2), 265\u2013304 (2010)","journal-title":"Comput. Complex."},{"key":"3_CR78","unstructured":"Sasson, E.B., et al.: Zerocash: decentralized anonymous payments from bitcoin. In: Symposium on Security and Privacy (2014)"},{"key":"3_CR79","doi-asserted-by":"crossref","unstructured":"Setty, S., Braun, B., Vu, V., Blumberg, A.J., Parno, B., Walfish, M.: Resolving the conflict between generality and plausibility in verified computation. In: EuroSys (2013)","DOI":"10.1145\/2465351.2465359"},{"key":"3_CR80","unstructured":"Setty, S.T., McPherson, R., Blumberg, A.J., Walfish, M.: Making argument systems for outsourced computation practical (sometimes). In: NDSS (2012)"},{"issue":"4","key":"3_CR81","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":"3","key":"3_CR82","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1145\/1467247.1467267","volume":"52","author":"M Sudan","year":"2009","unstructured":"Sudan, M.: Probabilistically checkable proofs. Commun. ACM 52(3), 76\u201384 (2009)","journal-title":"Commun. ACM"},{"key":"3_CR83","doi-asserted-by":"crossref","unstructured":"Wahby, R.S., Tzialla, I., Shelat, A., Thaler, J., Walfish, M.: Doubly-efficient zkSNARKs without trusted setup (2018)","DOI":"10.1109\/SP.2018.00060"},{"key":"3_CR84","unstructured":"Williams, R.: Strong ETH breaks with Merlin and Arthur: short non-interactive proofs of batch evaluation. arXiv preprint arXiv:1601.04743 (2016)"},{"key":"3_CR85","doi-asserted-by":"crossref","unstructured":"Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: vSQL: verifying arbitrary SQL queries over dynamic outsourced databases. In: Symposium on Security and Privacy (2017)","DOI":"10.1109\/SP.2017.43"},{"key":"3_CR86","unstructured":"Zhang, Y., Genkin, D., Katz, J., Papadopoulos, D., Papamanthou, C.: A zero-knowledge version of vSQL. Cryptology ePrint Archive, Report 2017\/1146 (2017)"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2019"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-26954-8_3","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,3,13]],"date-time":"2024-03-13T17:18:19Z","timestamp":1710350299000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-030-26954-8_3"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030269531","9783030269548"],"references-count":86,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-26954-8_3","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"1 August 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"CRYPTO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Cryptology Conference","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Santa Barbara, CA","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":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22 August 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"39","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2019\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"IACR websubrev","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"378","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"81","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"21% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"3","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"22","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}