{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T02:34:52Z","timestamp":1743042892012,"version":"3.40.3"},"publisher-location":"Cham","reference-count":33,"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_14","type":"book-chapter","created":{"date-parts":[[2017,11,4]],"date-time":"2017-11-04T02:43:27Z","timestamp":1509763407000},"page":"424-458","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":4,"title":["Near-Optimal Secret Sharing and Error Correcting Codes in $$\\mathsf {AC}^0$$"],"prefix":"10.1007","author":[{"given":"Kuan","family":"Cheng","sequence":"first","affiliation":[]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[]},{"given":"Xin","family":"Li","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2017,11,5]]},"reference":[{"issue":"2","key":"14_CR1","doi-asserted-by":"publisher","first-page":"509","DOI":"10.1109\/18.119713","volume":"38","author":"N Alon","year":"1992","unstructured":"Alon, N., Bruck, J., Naor, J., Naor, M., Roth, R.M.: Construction of asymptotically good low-rate error-correcting codes through pseudo-random graphs. IEEE Trans. Inf. Theory 38(2), 509\u2013516 (1992)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"4","key":"14_CR2","doi-asserted-by":"publisher","first-page":"845","DOI":"10.1137\/S0097539705446950","volume":"36","author":"B Applebaum","year":"2006","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: Cryptography in NC0. SIAM J. Comput. 36(4), 845\u2013888 (2006)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"14_CR3","doi-asserted-by":"publisher","first-page":"38","DOI":"10.1007\/s00037-007-0237-6","volume":"17","author":"B Applebaum","year":"2008","unstructured":"Applebaum, B., Ishai, Y., Kushilevitz, E.: On pseudorandom generators with linear stretch in NC0. Comput. Complex. 17(1), 38\u201369 (2008)","journal-title":"Comput. Complex."},{"key":"14_CR4","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090","volume-title":"Computational Complexity: A Modern Approach","author":"S Arora","year":"2009","unstructured":"Arora, S., Barak, B.: Computational Complexity: A Modern Approach. Cambridge University Press, Cambridge (2009)"},{"key":"14_CR5","doi-asserted-by":"crossref","DOI":"10.1142\/7438","volume-title":"Theory of Randomized Search Heuristics: Foundations and Recent Developments","author":"A Auger","year":"2011","unstructured":"Auger, A., Doerr, B.: Theory of Randomized Search Heuristics: Foundations and Recent Developments, vol. 1. World Scientific, Singapore (2011)"},{"key":"14_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"58","DOI":"10.1007\/978-3-662-49890-3_3","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"A Bishop","year":"2016","unstructured":"Bishop, A., Pastro, V., Rajaraman, R., Wichs, D.: Essentially optimal robust secret sharing with maximal corruptions. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 58\u201386. Springer, Heidelberg (2016). \n                      https:\/\/doi.org\/10.1007\/978-3-662-49890-3_3"},{"key":"14_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"593","DOI":"10.1007\/978-3-662-53015-3_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2016","author":"A Bogdanov","year":"2016","unstructured":"Bogdanov, A., Ishai, Y., Viola, E., Williamson, C.: Bounded indistinguishability and the complexity of recovering secrets. In: Robshaw, M., Katz, J. (eds.) CRYPTO 2016. LNCS, vol. 9816, pp. 593\u2013618. Springer, Heidelberg (2016). \n                      https:\/\/doi.org\/10.1007\/978-3-662-53015-3_21"},{"key":"14_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"365","DOI":"10.1007\/978-3-662-49096-9_15","volume-title":"Theory of Cryptography","author":"A Bogdanov","year":"2016","unstructured":"Bogdanov, A., Lee, C.H.: Homomorphic evaluation requires depth. In: Kushilevitz, E., Malkin, T. (eds.) TCC 2016. LNCS, vol. 9562, pp. 365\u2013371. Springer, Heidelberg (2016). \n                      https:\/\/doi.org\/10.1007\/978-3-662-49096-9_15"},{"key":"14_CR9","unstructured":"Bogdanov, A., Williamson, C.: Approximate bounded indistinguishability. In: ICALP (2017)"},{"key":"14_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/978-3-662-46803-6_12","volume-title":"Advances in Cryptology - EUROCRYPT 2015","author":"E Boyle","year":"2015","unstructured":"Boyle, E., Gilboa, N., Ishai, Y.: Function secret sharing. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 337\u2013367. Springer, Heidelberg (2015). \n                      https:\/\/doi.org\/10.1007\/978-3-662-46803-6_12"},{"key":"14_CR11","doi-asserted-by":"crossref","unstructured":"Bun, M., Thaler, J.: A nearly optimal lower bound on the approximate degree of AC0. In: FOCS (2017)","DOI":"10.1109\/FOCS.2017.10"},{"key":"14_CR12","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"291","DOI":"10.1007\/978-3-540-72540-4_17","volume-title":"Advances in Cryptology - EUROCRYPT 2007","author":"H Chen","year":"2007","unstructured":"Chen, H., Cramer, R., Goldwasser, S., de Haan, R., Vaikuntanathan, V.: Secure computation from random error correcting codes. In: Naor, M. (ed.) EUROCRYPT 2007. LNCS, vol. 4515, pp. 291\u2013310. Springer, Heidelberg (2007). \n                      https:\/\/doi.org\/10.1007\/978-3-540-72540-4_17"},{"key":"14_CR13","unstructured":"Cheng, K., Ishai, Y., Li, X.: Near-optimal secret sharing and error correcting codes in AC0. Cryptology ePrint Archive, Report 2017\/927 (2017). \n                      http:\/\/eprint.iacr.org\/2017\/927"},{"key":"14_CR14","unstructured":"Cheng, K., Li, X.: Randomness extraction in AC0 and with small locality. arXiv preprint \n                      arXiv:1602.01530\n                      \n                     (2016)"},{"key":"14_CR15","doi-asserted-by":"crossref","unstructured":"Cheraghchi, M.: Nearly optimal robust secret sharing. In: 2016 IEEE International Symposium on Information Theory (ISIT), pp. 2509\u20132513. IEEE (2016)","DOI":"10.1109\/ISIT.2016.7541751"},{"key":"14_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"272","DOI":"10.1007\/3-540-44683-4_24","volume-title":"Mathematical Foundations of Computer Science 2001","author":"M Cryan","year":"2001","unstructured":"Cryan, M., Miltersen, P.B.: On pseudorandom generators in NC0. In: Sgall, J., Pultr, A., Kolman, P. (eds.) MFCS 2001. LNCS, vol. 2136, pp. 272\u2013284. Springer, Heidelberg (2001). \n                      https:\/\/doi.org\/10.1007\/3-540-44683-4_24"},{"key":"14_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1007\/978-3-540-85174-5_14","volume-title":"Advances in Cryptology \u2013 CRYPTO 2008","author":"I Damg\u00e5rd","year":"2008","unstructured":"Damg\u00e5rd, I., Ishai, Y., Kr\u00f8igaard, M., Nielsen, J.B., Smith, A.: Scalable multiparty computation with nearly optimal work and resilience. In: Wagner, D. (ed.) CRYPTO 2008. LNCS, vol. 5157, pp. 241\u2013261. Springer, Heidelberg (2008). \n                      https:\/\/doi.org\/10.1007\/978-3-540-85174-5_14"},{"key":"14_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"76","DOI":"10.1007\/978-3-642-22670-0_10","volume-title":"Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation","author":"O Goldreich","year":"2011","unstructured":"Goldreich, O.: Candidate one-way functions based on expander graphs. In: Goldreich, O. (ed.) Studies in Complexity and Cryptography. Miscellanea on the Interplay between Randomness and Computation. LNCS, vol. 6650, pp. 76\u201387. Springer, Heidelberg (2011). \n                      https:\/\/doi.org\/10.1007\/978-3-642-22670-0_10"},{"key":"14_CR19","doi-asserted-by":"crossref","unstructured":"Goldwasser, S., Gutfreund, D., Healy, A., Kaufman, T., Rothblum, G.N.: Verifying and decoding in constant depth. In: STOC, pp. 440\u2013449. ACM (2007)","DOI":"10.1145\/1250790.1250855"},{"issue":"4","key":"14_CR20","doi-asserted-by":"publisher","first-page":"35","DOI":"10.1145\/2936015","volume":"63","author":"V Guruswami","year":"2016","unstructured":"Guruswami, V., Smith, A.: Optimal rate code constructions for computationally simple channels. J. ACM (JACM) 63(4), 35 (2016)","journal-title":"J. ACM (JACM)"},{"issue":"4","key":"14_CR21","doi-asserted-by":"publisher","first-page":"20","DOI":"10.1145\/1538902.1538904","volume":"56","author":"V Guruswami","year":"2009","unstructured":"Guruswami, V., Umans, C., Vadhan, S.: Unbalanced expanders and randomness extractors from Parvaresh-Vardy codes. J. ACM 56(4), 20 (2009)","journal-title":"J. ACM"},{"key":"14_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"405","DOI":"10.1007\/3-540-54233-7_151","volume-title":"Automata, Languages and Programming","author":"T Hagerup","year":"1991","unstructured":"Hagerup, T.: Fast parallel generation of random permutations. In: Albert, J.L., Monien, B., Artalejo, M.R. (eds.) ICALP 1991. LNCS, vol. 510, pp. 405\u2013416. Springer, Heidelberg (1991). \n                      https:\/\/doi.org\/10.1007\/3-540-54233-7_151"},{"key":"14_CR23","unstructured":"Lee, C.H., Viola, E.: Some limitations of the sum of small-bias distributions. In: ECCC, vol. 22, p. 5. Citeseer (2015)"},{"key":"14_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"28","DOI":"10.1007\/978-3-662-49890-3_2","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2016","author":"H Lin","year":"2016","unstructured":"Lin, H.: Indistinguishability obfuscation from constant-degree graded encoding schemes. In: Fischlin, M., Coron, J.-S. (eds.) EUROCRYPT 2016. LNCS, vol. 9665, pp. 28\u201357. Springer, Heidelberg (2016). \n                      https:\/\/doi.org\/10.1007\/978-3-662-49890-3_2"},{"key":"14_CR25","doi-asserted-by":"crossref","unstructured":"Lovett, S., Viola, E.: Bounded-depth circuits cannot sample good codes. In: CCC, pp. 243\u2013251. IEEE (2011)","DOI":"10.1109\/CCC.2011.11"},{"key":"14_CR26","doi-asserted-by":"crossref","unstructured":"Matias, Y., Vishkin, U.: Converting high probability into nearly-constant time with applications to parallel hashing. In: STOC, pp. 307\u2013316. ACM (1991)","DOI":"10.1145\/103418.103453"},{"issue":"6","key":"14_CR27","doi-asserted-by":"publisher","first-page":"46:1","DOI":"10.1145\/2792978","volume":"62","author":"E Miles","year":"2015","unstructured":"Miles, E., Viola, E.: Substitution-permutation networks, pseudorandom functions, and natural proofs. J. ACM 62(6), 46:1\u201346:29 (2015)","journal-title":"J. ACM"},{"key":"14_CR28","volume-title":"Perceptrons","author":"M Minsky","year":"1988","unstructured":"Minsky, M., Papert, S.: Perceptrons. MIT Press, Cambridge (1988)"},{"issue":"1","key":"14_CR29","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1002\/rsa.20112","volume":"29","author":"E Mossel","year":"2006","unstructured":"Mossel, E., Shpilka, A., Trevisan, L.: On $$\\varepsilon $$-biased generators in NC0. Random Struct. Algorithms 29(1), 56\u201381 (2006)","journal-title":"Random Struct. Algorithms"},{"issue":"2","key":"14_CR30","doi-asserted-by":"publisher","first-page":"336","DOI":"10.1006\/jcss.1998.1618","volume":"58","author":"M Naor","year":"1999","unstructured":"Naor, M., Reingold, O.: Synthesizers and their application to the parallel construction of pseudo-random functions. J. Comput. Syst. Sci. 58(2), 336\u2013375 (1999)","journal-title":"J. Comput. Syst. Sci."},{"issue":"11","key":"14_CR31","doi-asserted-by":"publisher","first-page":"612","DOI":"10.1145\/359168.359176","volume":"22","author":"A Shamir","year":"1979","unstructured":"Shamir, A.: How to share a secret. Commun. ACM 22(11), 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"issue":"3","key":"14_CR32","doi-asserted-by":"publisher","first-page":"337","DOI":"10.1007\/s00037-009-0267-3","volume":"18","author":"E Viola","year":"2009","unstructured":"Viola, E.: On approximate majority and probabilistic time. Comput. Complex. 18(3), 337 (2009)","journal-title":"Comput. Complex."},{"key":"14_CR33","doi-asserted-by":"publisher","first-page":"191","DOI":"10.1137\/100814998","volume":"41","author":"E Viola","year":"2012","unstructured":"Viola, E.: The complexity of distributions. SIAM J. Comput. 41, 191\u2013218 (2012)","journal-title":"SIAM J. Comput."}],"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_14","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,11,4]],"date-time":"2020-11-04T01:17:33Z","timestamp":1604452653000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-70503-3_14"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2017]]},"ISBN":["9783319705026","9783319705033"],"references-count":33,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-70503-3_14","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"}]}}