{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,20]],"date-time":"2026-01-20T14:27:15Z","timestamp":1768919235647,"version":"3.49.0"},"publisher-location":"Cham","reference-count":64,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031158018","type":"print"},{"value":"9783031158025","type":"electronic"}],"license":[{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2022,1,1]],"date-time":"2022-01-01T00:00:00Z","timestamp":1640995200000},"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":[[2022]]},"DOI":"10.1007\/978-3-031-15802-5_6","type":"book-chapter","created":{"date-parts":[[2022,10,11]],"date-time":"2022-10-11T16:59:52Z","timestamp":1665507592000},"page":"148-177","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":7,"title":["(Nondeterministic) Hardness vs. Non-malleability"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4236-3710","authenticated-orcid":false,"given":"Marshall","family":"Ball","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6797-641X","authenticated-orcid":false,"given":"Dana","family":"Dachman-Soled","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7979-3810","authenticated-orcid":false,"given":"Julian","family":"Loss","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2022,10,12]]},"reference":[{"key":"6_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Dodis, Y., Kazana, T., Obremski, M.: Non-malleable reductions and applications. In: Servedio, R.A., Rubinfeld, R. (eds.) Proceedings of the 47th Annual ACM Symposium on Theory of Computing, Portland, 14\u201317 June 2015, pp. 459\u2013468. ACM Press (2015)","DOI":"10.1145\/2746539.2746544"},{"issue":"2","key":"6_CR2","doi-asserted-by":"publisher","first-page":"524","DOI":"10.1137\/140985251","volume":"47","author":"D Aggarwal","year":"2018","unstructured":"Aggarwal, D., Dodis, Y., Lovett, S.: Non-malleable codes from additive combinatorics. SIAM J. Comput. 47(2), 524\u2013546 (2018)","journal-title":"SIAM J. Comput."},{"key":"6_CR3","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Kanukurthi, B., Obbattu, S.L.B., Obremski, M., Sekar, S.: Rate one-third non-malleable codes. In: IACR Cryptology ePrint Archive, p. 1042 (2021)","DOI":"10.1145\/3519935.3519972"},{"key":"6_CR4","doi-asserted-by":"crossref","unstructured":"Aggarwal, D., Obremski, M.: A constant rate non-malleable code in the split-state model. In: Proceedings of the 61st Annual Symposium on Foundations of Computer Science, Durham, 16\u201319 November 2020, pp. 1285\u20131294. IEEE Computer Society Press (2020)","DOI":"10.1109\/FOCS46700.2020.00122"},{"key":"6_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"538","DOI":"10.1007\/978-3-662-47989-6_26","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"S Agrawal","year":"2015","unstructured":"Agrawal, S., Gupta, D., Maji, H.K., Pandey, O., Prabhakaran, M.: Explicit non-malleable codes against bit-wise tampering and permutations. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9215, pp. 538\u2013557. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-47989-6_26"},{"key":"6_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"375","DOI":"10.1007\/978-3-662-46494-6_16","volume-title":"Theory of Cryptography","author":"S Agrawal","year":"2015","unstructured":"Agrawal, S., Gupta, D., Maji, H.K., Pandey, O., Prabhakaran, M.: A rate-optimizing compiler for non-malleable codes against bit-wise tampering and permutations. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 375\u2013397. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46494-6_16"},{"issue":"2","key":"6_CR7","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/s00037-016-0128-9","volume":"25","author":"B Applebaum","year":"2016","unstructured":"Applebaum, B., Artemenko, S., Shaltiel, R., Yang, G.: Incompressible functions, relative-error extractors, and the power of nondeterministic reductions. Comput. Complex. 25(2), 349\u2013418 (2016)","journal-title":"Comput. Complex."},{"key":"6_CR8","doi-asserted-by":"crossref","unstructured":"Babai, L.: Trading group theory for randomness. In: 17th Annual ACM Symposium on Theory of Computing, Providence, 6\u20138 May 1985, pp. 421\u2013429. ACM Press (1985)","DOI":"10.1145\/22145.22192"},{"issue":"2","key":"6_CR9","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":"6_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1007\/978-3-030-56877-1_4","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"M Ball","year":"2020","unstructured":"Ball, M., Chattopadhyay, E., Liao, J.-J., Malkin, T., Tan, L.-Y.: Non-malleability against polynomial tampering. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 97\u2013126. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56877-1_4"},{"key":"6_CR11","doi-asserted-by":"crossref","unstructured":"Ball, M., Dachman-Soled, D., Guo, S., Malkin, T., Tan, L.-Y.: Non-malleable codes for small-depth circuits. In: Thorup, M. (ed.) Proceedings of the 59th Annual Symposium on Foundations of Computer Science, Paris, 7\u20139 October 2018, pp. 826\u2013837. IEEE Computer Society Press (2018)","DOI":"10.1109\/FOCS.2018.00083"},{"key":"6_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/978-3-030-17653-2_17","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2019","author":"M Ball","year":"2019","unstructured":"Ball, M., Dachman-Soled, D., Kulkarni, M., Lin, H., Malkin, T.: Non-malleable codes against bounded polynomial time tampering. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019. LNCS, vol. 11476, pp. 501\u2013530. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-17653-2_17"},{"key":"6_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"881","DOI":"10.1007\/978-3-662-49896-5_31","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"M Ball","year":"2016","unstructured":"Ball, M., Dachman-Soled, D., Kulkarni, M., Malkin, T.: Non-malleable codes for bounded depth, bounded fan-in circuits. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9666, pp. 881\u2013908. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-49896-5_31"},{"key":"6_CR14","doi-asserted-by":"publisher","unstructured":"Ball, M., Dachman-Soled, D., Kulkarni, M., Malkin, T.: Non-malleable codes from average-case hardness: $${\\sf AC}^0$$, decision trees, and streaming space-bounded tampering. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 618\u2013650. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78372-7_20","DOI":"10.1007\/978-3-319-78372-7_20"},{"key":"6_CR15","unstructured":"Ball, M., Dachman-Soled, D., Kulkarni, M., Malkin, T.: Limits to non-malleability. In: Vidick, T. (ed.) Proceedings of the ITCS 2020: 11th Innovations in Theoretical Computer Science Conference, Seattle, 12\u201314 January 2020, vol. 151, pp. 80:1\u201380:32. LIPIcs (2020)"},{"key":"6_CR16","doi-asserted-by":"crossref","unstructured":"Ball, M., Dachman-Soled, D., Loss, J.: (Nondeterministic) hardness vs. non-malleability. In: IACR Cryptology ePrint Archive, p. 70 (2022)","DOI":"10.1007\/978-3-031-15802-5_6"},{"key":"6_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"413","DOI":"10.1007\/978-3-030-26948-7_15","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"M Ball","year":"2019","unstructured":"Ball, M., Guo, S., Wichs, D.: Non-malleable codes for decision trees. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 413\u2013434. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26948-7_15"},{"key":"6_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-22792-9_1","volume-title":"Advances in Cryptology \u2013 CRYPTO 2011","author":"B Barak","year":"2011","unstructured":"Barak, B., Dodis, Y., Krawczyk, H., Pereira, O., Pietrzak, K., Standaert, F.-X., Yu, Yu.: Leftover hash lemma, revisited. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 1\u201320. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-22792-9_1"},{"key":"6_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"299","DOI":"10.1007\/978-3-540-45146-4_18","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"B Barak","year":"2003","unstructured":"Barak, B., Ong, S.J., Vadhan, S.: Derandomization in cryptography. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 299\u2013315. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45146-4_18"},{"issue":"2","key":"6_CR20","doi-asserted-by":"publisher","first-page":"510","DOI":"10.1006\/inco.2000.2885","volume":"163","author":"M Bellare","year":"2000","unstructured":"Bellare, M., Goldreich, O., Petrank, E.: Uniform generation of NP-witnesses using an NP-oracle. Inf. Comput. 163(2), 510\u2013526 (2000)","journal-title":"Inf. Comput."},{"key":"6_CR21","doi-asserted-by":"crossref","unstructured":"Bitansky, N., Kalai, Y.T., Paneth, O.: Multi-collision resistance: a paradigm for keyless hash functions. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) Proceedings of the 50th Annual ACM Symposium on Theory of Computing, Los Angeles, 25\u201329 June 2018, pp. 671\u2013684. ACM Press (2018)","DOI":"10.1145\/3188745.3188870"},{"key":"6_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"127","DOI":"10.1007\/978-3-030-56877-1_5","volume-title":"Advances in Cryptology \u2013 CRYPTO 2020","author":"G Brian","year":"2020","unstructured":"Brian, G., Faonio, A., Obremski, M., Simkin, M., Venturi, D.: Non-malleable secret sharing against bounded joint-tampering attacks in the plain model. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020. LNCS, vol. 12172, pp. 127\u2013155. Springer, Cham (2020). https:\/\/doi.org\/10.1007\/978-3-030-56877-1_5"},{"key":"6_CR23","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, E., Goyal, V., Li, X.: Non-malleable extractors and codes, with their many tampered extensions. In: Wichs, D., Mansour, Y. (eds.) Proceedings of the 48th Annual ACM Symposium on Theory of Computing, Cambridge, 18\u201321 June 2016, pp. 285\u2013298. ACM Press (2018)","DOI":"10.1145\/2897518.2897547"},{"key":"6_CR24","doi-asserted-by":"crossref","unstructured":"Chattopadhyay, E., Li, X.: Non-malleable codes and extractors for small-depth circuits, and affine functions. In: Hatami, H., McKenzie, P., King, V. (eds.) Proceedings of the 49th Annual ACM Symposium on Theory of Computing, Montreal, 19\u201323 June 2017, pp. 1171\u20131184. ACM Press (2017)","DOI":"10.1145\/3055399.3055483"},{"key":"6_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"467","DOI":"10.1007\/978-3-030-26948-7_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2019","author":"B Chen","year":"2019","unstructured":"Chen, B., Chen, Y., Host\u00e1kov\u00e1, K., Mukherjee, P.: Continuous space-bounded non-malleable codes from stronger proofs-of-space. In: Boldyreva, A., Micciancio, D. (eds.) CRYPTO 2019. LNCS, vol. 11692, pp. 467\u2013495. Springer, Cham (2019). https:\/\/doi.org\/10.1007\/978-3-030-26948-7_17"},{"key":"6_CR26","doi-asserted-by":"crossref","unstructured":"Cheraghchi, M., Guruswami, V.: Capacity of non-malleable codes. In: Naor, M. (ed.) Proceedings of the ITCS 2014: 5th Conference on Innovations in Theoretical Computer Science, Princeton, 12\u201314 January 2014, pp. 155\u2013168. Association for Computing Machinery (2014)","DOI":"10.1145\/2554797.2554814"},{"key":"6_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"440","DOI":"10.1007\/978-3-642-54242-8_19","volume-title":"Theory of Cryptography","author":"M Cheraghchi","year":"2014","unstructured":"Cheraghchi, M., Guruswami, V.: Non-malleable coding against bit-wise and split-state tampering. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 440\u2013464. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_19"},{"key":"6_CR28","unstructured":"Dachman-Soled, D., Komargodski, I., Pass, R.: Non-malleable codes for bounded polynomial depth tampering. Cryptology ePrint Archive, Report 2020\/776 (2020). https:\/\/eprint.iacr.org\/2020\/776"},{"key":"6_CR29","doi-asserted-by":"publisher","unstructured":"Dachman-Soled, D., Komargodski, I., Pass, R.: Non-malleable codes for bounded parallel-time tampering. In: Malkin, T., Peikert, C. (eds.) CRYPTO 2021. LNCS, vol. 12827, pp. 535\u2013565. Springer, Cham (2021). https:\/\/doi.org\/10.1007\/978-3-030-84252-9_18","DOI":"10.1007\/978-3-030-84252-9_18"},{"key":"6_CR30","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"427","DOI":"10.1007\/978-3-662-46494-6_18","volume-title":"Theory of Cryptography","author":"D Dachman-Soled","year":"2015","unstructured":"Dachman-Soled, D., Liu, F.-H., Shi, E., Zhou, H.-S.: Locally decodable and updatable non-malleable codes and their applications. In: Dodis, Y., Nielsen, J.B. (eds.) TCC 2015. LNCS, vol. 9014, pp. 427\u2013450. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-46494-6_18"},{"key":"6_CR31","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-36594-2_1","volume-title":"Theory of Cryptography","author":"Y Dodis","year":"2013","unstructured":"Dodis, Y., Yu, Yu.: Overcoming weak expectations. In: Sahai, A. (ed.) TCC 2013. LNCS, vol. 7785, pp. 1\u201322. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-36594-2_1"},{"key":"6_CR32","doi-asserted-by":"crossref","unstructured":"Drucker, A.: Nondeterministic direct product reductions and the success probability of SAT solvers. In: 54th Annual Symposium on Foundations of Computer Science, Berkeley, 26\u201329 October 2013, pp. 736\u2013745. IEEE Computer Society Press (2013)","DOI":"10.1109\/FOCS.2013.84"},{"key":"6_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"239","DOI":"10.1007\/978-3-642-40084-1_14","volume-title":"Advances in Cryptology \u2013 CRYPTO 2013","author":"S Dziembowski","year":"2013","unstructured":"Dziembowski, S., Kazana, T., Obremski, M.: Non-malleable codes from two-source extractors. In: Canetti, R., Garay, J.A. (eds.) CRYPTO 2013. LNCS, vol. 8043, pp. 239\u2013257. Springer, Heidelberg (2013). https:\/\/doi.org\/10.1007\/978-3-642-40084-1_14"},{"key":"6_CR34","unstructured":"Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. In: Yao, A.C.-C. (ed.) ICS 2010: 1st Innovations in Computer Science, Tsinghua University, Beijing, 5\u20137 January 2010, pp. 434\u2013452. Tsinghua University Press (2010)"},{"issue":"4","key":"6_CR35","doi-asserted-by":"publisher","first-page":"20:1","DOI":"10.1145\/3178432","volume":"65","author":"S Dziembowski","year":"2018","unstructured":"Dziembowski, S., Pietrzak, K., Wichs, D.: Non-malleable codes. J. ACM 65(4), 20:1-20:32 (2018)","journal-title":"J. ACM"},{"key":"6_CR36","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"95","DOI":"10.1007\/978-3-319-63715-0_4","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"S Faust","year":"2017","unstructured":"Faust, S., Host\u00e1kov\u00e1, K., Mukherjee, P., Venturi, D.: Non-malleable codes for space-bounded tampering. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10402, pp. 95\u2013126. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63715-0_4"},{"key":"6_CR37","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/978-3-642-54242-8_20","volume-title":"Theory of Cryptography","author":"S Faust","year":"2014","unstructured":"Faust, S., Mukherjee, P., Nielsen, J.B., Venturi, D.: Continuous non-malleable codes. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 465\u2013488. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_20"},{"key":"6_CR38","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"111","DOI":"10.1007\/978-3-642-55220-5_7","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"S Faust","year":"2014","unstructured":"Faust, S., Mukherjee, P., Venturi, D., Wichs, D.: Efficient non-malleable codes and key-derivation for poly-size tampering circuits. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 111\u2013128. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-55220-5_7"},{"issue":"2","key":"6_CR39","doi-asserted-by":"publisher","first-page":"101","DOI":"10.1007\/BF01262928","volume":"6","author":"U Feige","year":"1997","unstructured":"Feige, U., Lund, C.: On the hardness of computing the permanent of random matrices. Comput. Complex. 6(2), 101\u2013132 (1997)","journal-title":"Comput. Complex."},{"issue":"3","key":"6_CR40","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 for all languages in NP have zero-knowledge proof systems. J. ACM 38(3), 691\u2013729 (1991)","journal-title":"J. ACM"},{"key":"6_CR41","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"209","DOI":"10.1007\/3-540-45726-7_17","volume-title":"Randomization and Approximation Techniques in Computer Science","author":"O Goldreich","year":"2002","unstructured":"Goldreich, O., Wigderson, A.: Derandomization that is rarely wrong from short advice that is typically good. In: Rolim, J.D.P., Vadhan, S. (eds.) RANDOM 2002. LNCS, vol. 2483, pp. 209\u2013223. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45726-7_17"},{"key":"6_CR42","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Sipser, M.: Private coins versus public coins in interactive proof systems. In: 18th Annual ACM Symposium on Theory of Computing, Berkeley, 28\u201330 May 1986, pp. 59\u201368. ACM Press (1986)","DOI":"10.1145\/12130.12137"},{"key":"6_CR43","doi-asserted-by":"crossref","unstructured":"Goyal, V., Kumar, A.: Non-malleable secret sharing. In: Diakonikolas, I., Kempe, D., Henzinger, M. (eds.) Proceedings of the 50th Annual ACM Symposium on Theory of Computing, Los Angeles, 25\u201329 June 2018, pp. 685\u2013698. ACM Press (2018)","DOI":"10.1145\/3188745.3188872"},{"key":"6_CR44","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"501","DOI":"10.1007\/978-3-319-96884-1_17","volume-title":"Advances in Cryptology \u2013 CRYPTO 2018","author":"V Goyal","year":"2018","unstructured":"Goyal, V., Kumar, A.: Non-malleable secret sharing for general access structures. In: Shacham, H., Boldyreva, A. (eds.) CRYPTO 2018. LNCS, vol. 10991, pp. 501\u2013530. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-96884-1_17"},{"issue":"3\u20134","key":"6_CR45","first-page":"85","volume":"12","author":"D Gutfreund","year":"2003","unstructured":"Gutfreund, D., Shaltiel, R., Ta-Shma, A.: Uniform hardness versus randomness tradeoffs for Arthur-Merlin games. Comput. Complex. 12(3\u20134), 85\u2013130 (2003)","journal-title":"Comput. Complex."},{"key":"6_CR46","doi-asserted-by":"crossref","unstructured":"Impagliazzo, R., Wigderson, A.: P = BPP if E requires exponential circuits: derandomizing the XOR lemma. In: 29th Annual ACM Symposium on Theory of Computing, El Paso, 4\u20136 May 1997, pp. 220\u2013229. ACM Press (1997)","DOI":"10.1145\/258533.258590"},{"key":"6_CR47","doi-asserted-by":"publisher","first-page":"169","DOI":"10.1016\/0304-3975(86)90174-X","volume":"43","author":"M Jerrum","year":"1986","unstructured":"Jerrum, M., Valiant, L.G., Vazirani, V.V.: Random generation of combinatorial structures from a uniform distribution. Theor. Comput. Sci. 43, 169\u2013188 (1986)","journal-title":"Theor. Comput. Sci."},{"key":"6_CR48","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/978-3-319-70503-3_11","volume-title":"Theory of Cryptography","author":"B Kanukurthi","year":"2017","unstructured":"Kanukurthi, B., Obbattu, S.L.B., Sekar, S.: Four-state non-malleable codes with explicit constant rate. In: Kalai, Y., Reyzin, L. (eds.) TCC 2017. LNCS, vol. 10678, pp. 344\u2013375. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-70503-3_11"},{"key":"6_CR49","doi-asserted-by":"publisher","unstructured":"Kanukurthi, B., Obbattu, S.L.B., Sekar, S.: Non-malleable randomness encoders and\u00a0their applications. In: Nielsen, J.B., Rijmen, V. (eds.) EUROCRYPT 2018. LNCS, vol. 10822, pp. 589\u2013617. Springer, Cham (2018). https:\/\/doi.org\/10.1007\/978-3-319-78372-7_19","DOI":"10.1007\/978-3-319-78372-7_19"},{"issue":"1","key":"6_CR50","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/s00037-011-0019-z","volume":"21","author":"J Kinne","year":"2012","unstructured":"Kinne, J., van Melkebeek, D., Shaltiel, R.: Pseudorandom generators, typically-correct derandomization, and circuit lower bounds. Comput. Complex. 21(1), 3\u201361 (2012)","journal-title":"Comput. Complex."},{"issue":"5","key":"6_CR51","doi-asserted-by":"publisher","first-page":"1501","DOI":"10.1137\/S0097539700389652","volume":"31","author":"AR Klivans","year":"2002","unstructured":"Klivans, A.R., van Melkebeek, D.: Graph nonisomorphism has subexponential size proofs unless the polynomial-time hierarchy collapses. SIAM J. Comput. 31(5), 1501\u20131526 (2002)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"6_CR52","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1137\/0215020","volume":"15","author":"LA Levin","year":"1986","unstructured":"Levin, L.A.: Average case complete problems. SIAM J. Comput. 15(1), 285\u2013286 (1986)","journal-title":"SIAM J. Comput."},{"key":"6_CR53","unstructured":"Li, F., Zuckerman, D.: Improved extractors for recognizable and algebraic sources. In: Achlioptas, D., V\u00e9gh, L.A. (eds.) Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques, APPROX\/RANDOM 2019, 20\u201322 September 2019, Massachusetts Institute of Technology, Cambridge, volume 145 of LIPIcs, pp. 72:1\u201372:22. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2019)"},{"key":"6_CR54","first-page":"115","volume":"23","author":"X Li","year":"2016","unstructured":"Li, X.: Improved non-malleable extractors, non-malleable codes and independent source extractors. Electron. Colloq. Comput. Complex. 23, 115 (2016)","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"6_CR55","doi-asserted-by":"crossref","unstructured":"Li, X.: Improved non-malleable extractors, non-malleable codes and independent source extractors. In Hatami, H., McKenzie, P., King, V. (eds.) Proceedings of the 49th Annual ACM Symposium on Theory of Computing, Montreal, 19\u201323 June 2017, pp. 1144\u20131156. ACM Press (2017)","DOI":"10.1145\/3055399.3055486"},{"key":"6_CR56","unstructured":"Li, X.: Non-malleable extractors and non-malleable codes: partially optimal constructions. In: Proceedings of the 34th Computational Complexity Conference, CCC 2019, New Brunswick, 18\u201320 July 2019, pp. 28:1\u201328:49 (2019)"},{"key":"6_CR57","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"517","DOI":"10.1007\/978-3-642-32009-5_30","volume-title":"Advances in Cryptology \u2013 CRYPTO 2012","author":"F-H Liu","year":"2012","unstructured":"Liu, F.-H., Lysyanskaya, A.: Tamper and leakage resilience in the split-state model. In: Safavi-Naini, R., Canetti, R. (eds.) CRYPTO 2012. LNCS, vol. 7417, pp. 517\u2013532. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-32009-5_30"},{"key":"6_CR58","doi-asserted-by":"crossref","unstructured":"Micali, S.: CS proofs (extended abstracts). In: 35th Annual Symposium on Foundations of Computer Science, Santa Fe, 20\u201322 November 1994, pp. 436\u2013453. IEEE Computer Society Press (1994)","DOI":"10.1109\/SFCS.1994.365746"},{"issue":"3","key":"6_CR59","doi-asserted-by":"publisher","first-page":"256","DOI":"10.1007\/s00037-005-0197-7","volume":"14","author":"PB Miltersen","year":"2005","unstructured":"Miltersen, P.B., Vinodchandran, N.V.: Derandomizing Arthur-Merlin games using hitting sets. Comput. Complex. 14(3), 256\u2013279 (2005)","journal-title":"Comput. Complex."},{"issue":"1","key":"6_CR60","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1007\/s00037-011-0006-4","volume":"20","author":"R Shaltiel","year":"2011","unstructured":"Shaltiel, R.: Weak derandomization of weak algorithms: explicit versions of Vao\u2019s lemma. Comput. Complex. 20(1), 87\u2013143 (2011)","journal-title":"Comput. Complex."},{"issue":"2","key":"6_CR61","doi-asserted-by":"publisher","first-page":"172","DOI":"10.1145\/1059513.1059516","volume":"52","author":"R Shaltiel","year":"2005","unstructured":"Shaltiel, R., Umans, C.: Simple extractors for all min-entropies and a new pseudorandom generator. J. ACM 52(2), 172\u2013216 (2005)","journal-title":"J. ACM"},{"issue":"4","key":"6_CR62","doi-asserted-by":"publisher","first-page":"298","DOI":"10.1007\/s00037-007-0218-9","volume":"15","author":"R Shaltiel","year":"2006","unstructured":"Shaltiel, R., Umans, C.: Pseudorandomness for approximate counting and sampling. Comput. Complex. 15(4), 298\u2013341 (2006)","journal-title":"Comput. Complex."},{"issue":"3","key":"6_CR63","doi-asserted-by":"publisher","first-page":"1006","DOI":"10.1137\/070698348","volume":"39","author":"R Shaltiel","year":"2009","unstructured":"Shaltiel, R., Umans, C.: Low-end uniform hardness versus randomness tradeoffs for AM. SIAM J. Comput. 39(3), 1006\u20131037 (2009)","journal-title":"SIAM J. Comput."},{"key":"6_CR64","doi-asserted-by":"crossref","unstructured":"Trevisan, L., Vadhan, S.P.: Extracting randomness from samplable distributions. In: 41st Annual Symposium on Foundations of Computer Science, Redondo Beach, 12\u201314 November 2000, pp. 32\u201342. IEEE Computer Society Press (2000)","DOI":"10.1109\/SFCS.2000.892063"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2022"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-15802-5_6","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,10]],"date-time":"2025-10-10T22:06:32Z","timestamp":1760133992000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-15802-5_6"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022]]},"ISBN":["9783031158018","9783031158025"],"references-count":64,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-15802-5_6","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022]]},"assertion":[{"value":"12 October 2022","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":"2022","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"15 August 2022","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2022","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"42","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2022","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/crypto.iacr.org\/2022\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}