{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,8,21]],"date-time":"2025-08-21T16:51:20Z","timestamp":1755795080408,"version":"3.44.0"},"publisher-location":"Cham","reference-count":62,"publisher":"Springer Nature Switzerland","isbn-type":[{"type":"print","value":"9783032019066"},{"type":"electronic","value":"9783032019073"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-032-01907-3_16","type":"book-chapter","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T22:27:39Z","timestamp":1755383259000},"page":"480-513","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["How to\u00a0Share an\u00a0NP Statement or\u00a0Combiners for\u00a0Zero-Knowledge Proofs"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4792-369X","authenticated-orcid":false,"given":"Benny","family":"Applebaum","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-5913-1636","authenticated-orcid":false,"given":"Eliran","family":"Kachlon","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,8,17]]},"reference":[{"key":"16_CR1","doi-asserted-by":"crossref","unstructured":"Ajtai, M., Koml\u00f3s, J., Szemer\u00e9di, E.: An $$O(n log n)$$ sorting network. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp.\u00a01\u20139 (1983)","DOI":"10.1145\/800061.808726"},{"key":"16_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"395","DOI":"10.1007\/978-3-319-96881-0_14","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"P Ananth","year":"2018","unstructured":"Ananth, P., Choudhuri, A.R., Goel, A., Jain, A.: Round-optimal secure multiparty computation with honest majority. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10992, pp. 395\u2013424. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96881-0_14"},{"key":"16_CR3","unstructured":"Applebaum, B., Kachlon, E.: How to share an NP statement or combiners for zero-knowledge proofs. Electron. Colloquium Comput. Complex. TR25-023 (2025)"},{"key":"16_CR4","unstructured":"Applebaum, B., Kachlon, E.: NIZK amplification via leakage-resilient secure computation (2025), to appear in Crypto 2025. Cryptology ePrint Archive, Paper 2025\/995 (2025)"},{"key":"16_CR5","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Kachlon, E., Patra, A.: Round-optimal honest-majority MPC in minicrypt and with everlasting security - (extended abstract). In: Kiltz, E., Vaikuntanathan, V. (eds.) Proceeding of TCC 2022, Chicago, IL, USA, 7\u201310 November 2022, Proceedings, Part II, LNCS, vol. 13748, pp. 103\u2013120. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-22365-5_4","DOI":"10.1007\/978-3-031-22365-5_4"},{"key":"16_CR6","doi-asserted-by":"publisher","unstructured":"Applebaum, B., Kachlon, E., Patra, A.: Verifiable relation sharing and multi-verifier zero-knowledge in two rounds: Trading nizks with honest majority - (extended abstract). In: Dodis, Y., Shrimpton, T. (eds.) Proceeding of CRYPTO \u201920, Part IV. LNCS, vol. 13510, pp. 33\u201356. Springer (2022). https:\/\/doi.org\/10.1007\/978-3-031-15985-5_2","DOI":"10.1007\/978-3-031-15985-5_2"},{"key":"16_CR7","doi-asserted-by":"crossref","unstructured":"Asharov, G., Jain, A., L\u00f3pez-Alt, A., Tromer, E., Vaikuntanathan, V., Wichs, D.: Multiparty computation with low communication, computation and interaction via threshold FHE. In: Proceeding of EUROCRYPT \u201920, pp. 483\u2013501 (2012)","DOI":"10.1007\/978-3-642-29011-4_29"},{"key":"16_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1007\/978-3-030-64840-4_5","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2020","author":"S Badrinarayanan","year":"2020","unstructured":"Badrinarayanan, S., Jain, A., Manohar, N., Sahai, A.: Secure MPC: laziness leads to GOD. In: Moriai, S., Wang, H. (eds.) ASIACRYPT 2020. LNCS, vol. 12493, pp. 120\u2013150. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64840-4_5"},{"key":"16_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"11","DOI":"10.1007\/978-3-642-20901-7_2","volume-title":"Coding and Cryptology","author":"A Beimel","year":"2011","unstructured":"Beimel, A.: Secret-sharing schemes: a survey. In: Chee, Y.M., et al. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11\u201346. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-20901-7_2"},{"key":"16_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"614","DOI":"10.1007\/3-540-39200-9_38","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2003","author":"M Bellare","year":"2003","unstructured":"Bellare, M., Micciancio, D., Warinschi, B.: Foundations of group signatures: formal definitions, simplified requirements, and a construction based on general assumptions. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 614\u2013629. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-39200-9_38"},{"key":"16_CR11","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":"16_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"27","DOI":"10.1007\/0-387-34799-2_3","volume-title":"Advances in Cryptology \u2014 CRYPTO\u2019 88","author":"J Benaloh","year":"1990","unstructured":"Benaloh, J., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 27\u201335. Springer, New York (1990). https:\/\/doi.org\/10.1007\/0-387-34799-2_3"},{"key":"16_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"60","DOI":"10.1007\/11681878_4","volume-title":"Theory of Cryptography","author":"A Bender","year":"2006","unstructured":"Bender, A., Katz, J., Morselli, R.: Ring signatures: stronger definitions, and constructions without random oracles. In: Halevi, S., Rabin, T. (eds.) TCC 2006. LNCS, vol. 3876, pp. 60\u201379. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11681878_4"},{"key":"16_CR14","doi-asserted-by":"publisher","unstructured":"Bitansky, N., Geier, N.: Amplification of non-interactive zero knowledge, revisited. In: Reyzin, L., Stebila, D. (eds.) Proceeding of CRYPTO \u201920, Part IX. LNCS, vol. 14928, pp. 361\u2013390. Springer (2024). https:\/\/doi.org\/10.1007\/978-3-031-68400-5_11","DOI":"10.1007\/978-3-031-68400-5_11"},{"key":"16_CR15","doi-asserted-by":"publisher","unstructured":"Blakley, G.R.: Safeguarding cryptographic keys. In: 1979 International Workshop on Managing Requirements Knowledge, MARK 1979, New York, NY, USA, 4\u20137 June 1979. pp. 313\u2013318. IEEE (1979). https:\/\/doi.org\/10.1109\/MARK.1979.8817296","DOI":"10.1109\/MARK.1979.8817296"},{"key":"16_CR16","doi-asserted-by":"crossref","unstructured":"Blum, M., Feldman, P., Micali, S.: Non-interactive zero-knowledge and its applications. In: Proceedings of the Twentieth Annual ACM Symposium on Theory of Computing, pp. 103\u2013112 (1988)","DOI":"10.1145\/62212.62222"},{"key":"16_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1007\/978-3-030-64375-1_23","volume-title":"Theory of Cryptography","author":"Z Brakerski","year":"2020","unstructured":"Brakerski, Z., Garg, S., Tsabary, R.: FHE-based bootstrapping of designated-prover NIZK. In: Pass, R., Pietrzak, K. (eds.) TCC 2020. LNCS, vol. 12550, pp. 657\u2013683. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-64375-1_23"},{"key":"16_CR18","doi-asserted-by":"crossref","unstructured":"Brakerski, Z., Koppula, V., Mour, T.: NIZK from LPN and trapdoor hash via correlation intractability for approximable relations. IACR Cryptol. ePrint Arch. p.\u00a0258 (2020)","DOI":"10.1007\/978-3-030-56877-1_26"},{"key":"16_CR19","doi-asserted-by":"crossref","unstructured":"Burmester, M., Desmedt, Y.: Broadcast interactive proofs (extended abstract). In: Proceeding of EUROCRYPT \u201991, pp. 81\u201395 (1991)","DOI":"10.1007\/3-540-46416-6_7"},{"key":"16_CR20","doi-asserted-by":"publisher","unstructured":"Canetti, R., et al.: Fiat-shamir: from practice to theory. In: Charikar, M., Cohen, E. (eds.) Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, Phoenix, AZ, USA, 23\u201326 June 2019, pp. 1082\u20131090. ACM (2019). https:\/\/doi.org\/10.1145\/3313276.3316380","DOI":"10.1145\/3313276.3316380"},{"key":"16_CR21","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"91","DOI":"10.1007\/978-3-319-78381-9_4","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2018","author":"R Canetti","year":"2018","unstructured":"Canetti, R., Chen, Y., Reyzin, L., Rothblum, R.D.: Fiat-Shamir and correlation intractability from strong KDM-secure encryption. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10820, pp. 91\u2013122. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78381-9_4"},{"key":"16_CR22","doi-asserted-by":"crossref","unstructured":"Canetti, R., Goldreich, O., Halevi, S.: The random oracle methodology, revisited. J. ACM 51(4), 557\u2013594 (2004)","DOI":"10.1145\/1008731.1008734"},{"key":"16_CR23","doi-asserted-by":"publisher","unstructured":"Chor, B., Kushilevitz, E.: A zero-one law for boolean privacy. In: Proceedings of the Twenty-First Annual ACM Symposium on Theory of Computing, STOC 1989, pp. 62\u201372. ACM, New York, NY, USA (1989). https:\/\/doi.org\/10.1145\/73007.73013","DOI":"10.1145\/73007.73013"},{"key":"16_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1007\/978-3-642-40084-1_11","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"G Cohen","year":"2013","unstructured":"Cohen, G., et al.: Efficient multiparty protocols via log-depth threshold formulae. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 185\u2013202. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40084-1_11"},{"key":"16_CR25","doi-asserted-by":"publisher","unstructured":"Damg\u00e5rd, I., Pedersen, T.P., Pfitzmann, B.: Statistical secrecy and multibit commitments. IEEE Trans. Inf. Theory 44(3), 1143\u20131151 (1998). https:\/\/doi.org\/10.1109\/18.669255","DOI":"10.1109\/18.669255"},{"key":"16_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"532","DOI":"10.1007\/978-3-662-45611-8_28","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2014","author":"G Danezis","year":"2014","unstructured":"Danezis, G., Fournet, C., Groth, J., Kohlweiss, M.: Square span programs with applications to succinct NIZK arguments. In: Sarkar, P., Iwata, T. (eds.) ASIACRYPT 2014. LNCS, vol. 8873, pp. 532\u2013550. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-45611-8_28"},{"key":"16_CR27","unstructured":"Ciampi, M., Magliocco, L., Venturi, D., Xia, Y.: Robust non-interactive zero-knowledge combiners. Cryptology ePrint Archive, Paper 2025\/240 (2025)"},{"key":"16_CR28","doi-asserted-by":"crossref","unstructured":"Dolev, D., Dwork, C., Naor, M.: Non-malleable cryptography. In: Proceedings of the Twenty-Third Annual ACM Symposium on Theory of Computing, pp. 542\u2013552 (1991)","DOI":"10.1145\/103418.103474"},{"key":"16_CR29","doi-asserted-by":"crossref","unstructured":"Dwork, C., Feige, U., Kilian, J., Naor, M., Safra, M.: Low communication 2-prover zero-knowledge proofs for np: Preliminary version. In: Annual International Cryptology Conference, pp. 215\u2013227. Springer (1992)","DOI":"10.1007\/3-540-48071-4_15"},{"key":"16_CR30","doi-asserted-by":"crossref","unstructured":"Dwork, C., Naor, M.: Zaps and their applications. SIAM J. Comput. 36(6), 1513\u20131543 (2007)","DOI":"10.1137\/S0097539703426817"},{"key":"16_CR31","unstructured":"Feige, U., Lapidot, D., Shamir, A.: Multiple non-interactive zero knowledge proofs based on a single random string. In: Proceedings [1990] 31st Annual Symposium on Foundations of Computer Science, pp. 308\u2013317. IEEE (1990)"},{"key":"16_CR32","doi-asserted-by":"publisher","unstructured":"Furst, M.L., Saxe, J.B., Sipser, M.: Parity, circuits, and the polynomial-time hierarchy. Math. Syst. Theory 17(1), 13\u201327 (1984). https:\/\/doi.org\/10.1007\/BF01744431","DOI":"10.1007\/BF01744431"},{"key":"16_CR33","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: Proceedings of the 19th Annual ACM Symposium on Theory of Computing, 1987, New York, New York, USA, pp. 218\u2013229 (1987)","DOI":"10.1145\/28395.28420"},{"issue":"1","key":"16_CR34","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BF00195207","volume":"7","author":"O Goldreich","year":"1994","unstructured":"Goldreich, O., Oren, Y.: Definitions and properties of zero-knowledge proof systems. J. Cryptol. 7(1), 1\u201332 (1994). https:\/\/doi.org\/10.1007\/BF00195207","journal-title":"J. Cryptol."},{"key":"16_CR35","doi-asserted-by":"publisher","unstructured":"Goldwasser, S., Micali, S., Rackoff, C.: The knowledge complexity of interactive proof systems. SIAM J. Comput. 18(1), 186\u2013208 (1989). https:\/\/doi.org\/10.1137\/0218012","DOI":"10.1137\/0218012"},{"key":"16_CR36","doi-asserted-by":"crossref","unstructured":"Gordon, S.D., Liu, F., Shi, E.: Constant-round MPC with fairness and guarantee of output delivery. In: Proceeding of CRYPTO \u201920, Part II, pp. 63\u201382 (2015)","DOI":"10.1007\/978-3-662-48000-7_4"},{"key":"16_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"608","DOI":"10.1007\/978-3-030-26951-7_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"V Goyal","year":"2019","unstructured":"Goyal, V., Jain, A., Sahai, A.: Simultaneous amplification: the case of non-interactive zero-knowledge. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11693, pp. 608\u2013637. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26951-7_21"},{"key":"16_CR38","doi-asserted-by":"publisher","unstructured":"Groth, J., Ostrovsky, R.: Cryptography in the multi-string model. J. Cryptol. 27(3), 506\u2013543 (2014). https:\/\/doi.org\/10.1007\/S00145-013-9152-Y","DOI":"10.1007\/S00145-013-9152-Y"},{"key":"16_CR39","doi-asserted-by":"publisher","unstructured":"Groth, J., Ostrovsky, R., Sahai, A.: New techniques for noninteractive zero-knowledge. J. ACM 59(3), 11:1\u201311:35 (2012). https:\/\/doi.org\/10.1145\/2220357.2220358","DOI":"10.1145\/2220357.2220358"},{"key":"16_CR40","doi-asserted-by":"publisher","unstructured":"Halevi, S., Micali, S.: Practical and provably-secure commitment schemes from collision-free hashing. In: Koblitz, N. (ed.) Proceeding of CRYPTO \u201996. LNCS, vol.\u00a01109, pp. 201\u2013215. Springer (1996). https:\/\/doi.org\/10.1007\/3-540-68697-5_16","DOI":"10.1007\/3-540-68697-5_16"},{"key":"16_CR41","doi-asserted-by":"publisher","unstructured":"Hirahara, S., Nanashima, M.: One-way functions and zero knowledge. In: Mohar, B., Shinkar, I., O\u2019Donnell, R. (eds.) Proceedings of the 56th Annual ACM Symposium on Theory of Computing, STOC 2024, Vancouver, BC, Canada, 24\u201328 June 2024, pp. 1731\u20131738. ACM (2024). https:\/\/doi.org\/10.1145\/3618260.3649701","DOI":"10.1145\/3618260.3649701"},{"key":"16_CR42","doi-asserted-by":"publisher","unstructured":"Hirt, M., Maurer, U.M.: Player simulation and general adversary structures in perfect multiparty computation. J. Cryptol. 13(1), 31\u201360 (2000). https:\/\/doi.org\/10.1007\/S001459910003","DOI":"10.1007\/S001459910003"},{"key":"16_CR43","doi-asserted-by":"crossref","unstructured":"Holmgren, J., Lombardi, A.: Cryptographic hashing from strong one-way functions (or: One-way product functions and their applications). In: 2018 IEEE 59th annual symposium on Foundations of Computer Science (FOCS), pp. 850\u2013858. IEEE (2018)","DOI":"10.1109\/FOCS.2018.00085"},{"key":"16_CR44","doi-asserted-by":"publisher","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Sahai, A.: Zero-knowledge proofs from secure multiparty computation. SIAM J. Comput. 39(3), 1121\u20131152 (2009). https:\/\/doi.org\/10.1137\/080725398","DOI":"10.1137\/080725398"},{"key":"16_CR45","unstructured":"Jain, A.: Aayush jain\u2019s website (2024), https:\/\/sites.google.com\/view\/aayushjain\/home"},{"key":"16_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"224","DOI":"10.1007\/978-3-319-63715-0_8","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"YT Kalai","year":"2017","unstructured":"Kalai, Y.T., Rothblum, G.N., Rothblum, R.D.: From obfuscation to the security of fiat-shamir for proofs. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 224\u2013251. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63715-0_8"},{"key":"16_CR47","doi-asserted-by":"crossref","unstructured":"Kilian, J., Petrank, E., Tardos, G.: Probabilistically checkable proofs with zero knowledge. In: Proceedings of the Twenty-Ninth Annual ACM Symposium on Theory of Computing, pp. 496\u2013505 (1997)","DOI":"10.1145\/258533.258643"},{"key":"16_CR48","doi-asserted-by":"crossref","unstructured":"Komargodski, I., Naor, M., Yogev, E.: Secret-sharing for np. In: International Conference on the Theory and Application of Cryptology and Information Security, pp. 254\u2013273. Springer (2014)","DOI":"10.1007\/978-3-662-45608-8_14"},{"key":"16_CR49","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"410","DOI":"10.1007\/978-3-030-45727-3_14","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2020","author":"B Libert","year":"2020","unstructured":"Libert, B., Passel\u00e8gue, A., Wee, H., Wu, D.J.: New constructions of statistical NIZKs: dual-mode DV-NIZKs and more. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020. LNCS, vol. 12107, pp. 410\u2013441. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-45727-3_14"},{"key":"16_CR50","doi-asserted-by":"publisher","unstructured":"Naor, M.: Bit commitment using pseudo-randomness. In: Brassard, G. (ed.) Proceeding of CRYPTO \u201989. LNCS, vol.\u00a0435, pp. 128\u2013136. Springer (1989). https:\/\/doi.org\/10.1007\/0-387-34805-0_13","DOI":"10.1007\/0-387-34805-0_13"},{"key":"16_CR51","doi-asserted-by":"crossref","unstructured":"Naor, M., Yung, M.: Public-key cryptosystems provably secure against chosen ciphertext attacks. In: Proceedings of the Twenty-Second Annual ACM Symposium on Theory of Computing, pp. 427\u2013437 (1990)","DOI":"10.1145\/100216.100273"},{"key":"16_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-540-73420-8_19","volume-title":"Automata, Languages and Programming","author":"R O\u2019Donnell","year":"2007","unstructured":"O\u2019Donnell, R., Wimmer, K.: Approximation by DNF: examples and counterexamples. In: Arge, L., Cachin, C., Jurdzi\u0144ski, T., Tarlecki, A. (eds.) ICALP 2007. LNCS, vol. 4596, pp. 195\u2013206. Springer, Heidelberg (2007). https:\/\/doi.org\/10.1007\/978-3-540-73420-8_19"},{"key":"16_CR53","doi-asserted-by":"publisher","unstructured":"Parno, B., Howell, J., Gentry, C., Raykova, M.: Pinocchio: nearly practical verifiable computation. Commun. ACM 59(2), 103\u2013112 (2016). https:\/\/doi.org\/10.1145\/2856449","DOI":"10.1145\/2856449"},{"key":"16_CR54","doi-asserted-by":"crossref","unstructured":"Paterson, M.S.: Improved sorting networks with $$O(\\log n)$$ depth. Algorithmica 5(1), 75\u201392 (1990)","DOI":"10.1007\/BF01840378"},{"key":"16_CR55","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"89","DOI":"10.1007\/978-3-030-26948-7_4","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"C Peikert","year":"2019","unstructured":"Peikert, C., Shiehian, S.: Noninteractive zero knowledge for NP from (Plain) learning with errors. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 89\u2013114. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26948-7_4"},{"key":"16_CR56","doi-asserted-by":"crossref","unstructured":"Sahai, A., Waters, B.: How to use indistinguishability obfuscation: deniable encryption, and more. In: Proceedings of the Forty-Sixth Annual ACM Symposium on Theory of Computing, pp. 475\u2013484 (2014)","DOI":"10.1145\/2591796.2591825"},{"key":"16_CR57","doi-asserted-by":"publisher","unstructured":"Santis, A.D., Micali, S., Persiano, G.: Non-interactive zero-knowledge proof systems. In: Pomerance, C. (ed.) Proceeding of CRYPTO \u201987, LNCS, vol.\u00a0293, pp. 52\u201372. Springer (1987). https:\/\/doi.org\/10.1007\/3-540-48184-2_5","DOI":"10.1007\/3-540-48184-2_5"},{"key":"16_CR58","unstructured":"Sasson, E.B., etal.: Zerocash: decentralized anonymous payments from bitcoin. In: 2014 IEEE Symposium on Security and Privacy, pp. 459\u2013474. IEEE (2014)"},{"key":"16_CR59","doi-asserted-by":"crossref","unstructured":"Seiferas, J.: Sorting networks of logarithmic depth, further simplified. Algorithmica 53, 374\u2013384 (2009)","DOI":"10.1007\/s00453-007-9025-6"},{"key":"16_CR60","doi-asserted-by":"crossref","unstructured":"Shamir, A.: How to share a secret. Commun. ACM 22(11), 612\u2013613 (1979)","DOI":"10.1145\/359168.359176"},{"key":"16_CR61","doi-asserted-by":"crossref","unstructured":"Spira, P.: On time-hardware complexity tradeoffs for boolean functions. In: Proceedings of the 4th Hawaii Symposium on System Sciences, 1971. pp. 525\u2013527 (1971)","DOI":"10.3109\/15563657108990975"},{"key":"16_CR62","doi-asserted-by":"publisher","unstructured":"Wegener, I.: Relating monotone formula size and monotone depth of boolean functions. Inf. Process. Lett. 16(1), 41\u201342 (1983). https:\/\/doi.org\/10.1016\/0020-0190(83)90011-X","DOI":"10.1016\/0020-0190(83)90011-X"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2025"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-01907-3_16","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T22:27:42Z","timestamp":1755383262000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-01907-3_16"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783032019066","9783032019073"],"references-count":62,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-01907-3_16","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"17 August 2025","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":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"17 August 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"21 August 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"45","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}