{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,27]],"date-time":"2025-03-27T13:35:21Z","timestamp":1743082521549,"version":"3.40.3"},"publisher-location":"Berlin, Heidelberg","reference-count":48,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"type":"print","value":"9783662530146"},{"type":"electronic","value":"9783662530153"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"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":[[2016]]},"DOI":"10.1007\/978-3-662-53015-3_21","type":"book-chapter","created":{"date-parts":[[2016,7,20]],"date-time":"2016-07-20T10:10:25Z","timestamp":1469009425000},"page":"593-618","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Bounded Indistinguishability and the Complexity of Recovering Secrets"],"prefix":"10.1007","author":[{"given":"Andrej","family":"Bogdanov","sequence":"first","affiliation":[]},{"given":"Yuval","family":"Ishai","sequence":"additional","affiliation":[]},{"given":"Emanuele","family":"Viola","sequence":"additional","affiliation":[]},{"given":"Christopher","family":"\u00a0Williamson","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,7,21]]},"reference":[{"key":"21_CR1","unstructured":"Aaronson, S.: A counterexample to the generalized Linial-Nisan conjecture. Electronic Colloquium on Computational Complexity, Technical report 109 (2010)"},{"issue":"4","key":"21_CR2","doi-asserted-by":"publisher","first-page":"595","DOI":"10.1145\/1008731.1008735","volume":"51","author":"S Aaronson","year":"2004","unstructured":"Aaronson, S., Shi, Y.: Quantum lower bounds for the collision and the element distinctness problems. J. ACM 51(4), 595\u2013605 (2004)","journal-title":"J. ACM"},{"key":"21_CR3","doi-asserted-by":"crossref","unstructured":"Ajtai, M.: Approximate counting with uniform constant-depth circuits. In: Advances in Computational Complexity Theory, pp. 1\u201320 (1993)","DOI":"10.1090\/dimacs\/013\/01"},{"issue":"2","key":"21_CR4","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. Theor. 38(2), 509\u2013516 (1992)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"3","key":"21_CR5","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/S0020-0190(03)00359-4","volume":"88","author":"N Alon","year":"2003","unstructured":"Alon, N., Goldreich, O., Mansour, Y.: Almost k-wise independence versus k-wise independence. Inf. Process. Lett. 88(3), 107\u2013110 (2003)","journal-title":"Inf. Process. Lett."},{"issue":"4","key":"21_CR6","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 NC$$^0$$. SIAM J. Comput. 36(4), 845\u2013888 (2006)","journal-title":"SIAM J. Comput."},{"issue":"6","key":"21_CR7","doi-asserted-by":"publisher","first-page":"2220","DOI":"10.1137\/070691954","volume":"38","author":"LMJ Bazzi","year":"2009","unstructured":"Bazzi, L.M.J.: Polylogarithmic independence can fool DNF formulas. SIAM J. Comput. 38(6), 2220\u20132272 (2009)","journal-title":"SIAM J. Comput."},{"key":"21_CR8","unstructured":"Bogdanov, A., Ishai, Y., Viola, E., Williamson, C.: Bounded indistinguishability, the complexity of recovering secrets. Electronic Colloquium on Computational Complexity (ECCC), vol. 22, p. 182 (2015)"},{"issue":"5","key":"21_CR9","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1754399.1754401","volume":"57","author":"M Braverman","year":"2010","unstructured":"Braverman, M.: Polylogarithmic independence fools AC$$^{\\text{0 }}$$ circuits. J. ACM 57(5), 1\u20136 (2010)","journal-title":"J. ACM"},{"issue":"4","key":"21_CR10","doi-asserted-by":"publisher","first-page":"379","DOI":"10.1007\/s00224-006-1313-z","volume":"40","author":"H Buhrman","year":"2007","unstructured":"Buhrman, H., Newman, I., R\u00f6hrig, H., de Wolf, R.: Robust polynomials and quantum algorithms. Theor. Comput. Syst. 40(4), 379\u2013395 (2007)","journal-title":"Theor. Comput. Syst."},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"303","DOI":"10.1007\/978-3-642-39206-1_26","volume-title":"Automata, Languages, and Programming","author":"M Bun","year":"2013","unstructured":"Bun, M., Thaler, J.: Dual lower bounds for approximate degree and Markov-Bernstein inequalities. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 303\u2013314. Springer, Heidelberg (2013)"},{"key":"21_CR12","unstructured":"Bun, M., Thaler, J.: Dual polynomials for collision and element distinctness (2015). \n                      www.eccc.uni-trier.de\/"},{"key":"21_CR13","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"466","DOI":"10.1007\/978-3-642-03356-8_28","volume-title":"Advances in Cryptology - CRYPTO 2009","author":"I Cascudo","year":"2009","unstructured":"Cascudo, I., Chen, H., Cramer, R., Xing, C.: Asymptotically good ideal linear secret sharing with strong multiplication over any fixed finite field. In: Halevi, S. (ed.) CRYPTO 2009. LNCS, vol. 5677, pp. 466\u2013486. Springer, Heidelberg (2009)"},{"issue":"1","key":"21_CR14","doi-asserted-by":"publisher","first-page":"81","DOI":"10.1006\/jcss.1999.1695","volume":"61","author":"S Chari","year":"2000","unstructured":"Chari, S., Rohatgi, P., Srinivasan, A.: Improved algorithms via approximations of probability distributions. J. Comput. Syst. Sci. 61(1), 81\u2013107 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR15","doi-asserted-by":"publisher","first-page":"97","DOI":"10.1093\/comjnl\/bxh152","volume":"49","author":"S Cimato","year":"2006","unstructured":"Cimato, S., Prisco, R.D., Santis, A.D.: Probabilistic visual cryptography schemes. Comput. J. 49, 97\u2013107 (2006)","journal-title":"Comput. J."},{"key":"21_CR16","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"313","DOI":"10.1007\/978-3-662-46803-6_11","volume-title":"Advances in Cryptology - EUROCRYPT 2015","author":"R Cramer","year":"2015","unstructured":"Cramer, R., Damg\u00e5rd, I.B., D\u00f6ttling, N., Fehr, S., Spini, G.: Linear secret sharing schemes from error correcting codes and universal hash functions. In: Oswald, E., Fischlin, M. (eds.) EUROCRYPT 2015. LNCS, vol. 9057, pp. 313\u2013336. Springer, Heidelberg (2015)"},{"key":"21_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"445","DOI":"10.1007\/978-3-642-13190-5_23","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2010","author":"I Damg\u00e5rd","year":"2010","unstructured":"Damg\u00e5rd, I., Ishai, Y., Kr\u00f8igaard, M.: Perfectly secure multiparty computation and the computational overhead of cryptography. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 445\u2013465. Springer, Heidelberg (2010)"},{"key":"21_CR18","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)"},{"issue":"8","key":"21_CR19","doi-asserted-by":"publisher","first-page":"3441","DOI":"10.1137\/100783030","volume":"39","author":"I Diakonikolas","year":"2010","unstructured":"Diakonikolas, I., Gopalan, P., Jaiswal, R., Servedio, R.A., Viola, E.: Bounded independence fools halfspaces. SIAM J. Comput. 39(8), 3441\u20133462 (2010)","journal-title":"SIAM J. Comput."},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Diakonikolas, I., Kane, D., Nelson, J.: Bounded independence fools degree-2 threshold functions. In: Proceedings of 51st FOCS (2010)","DOI":"10.1109\/FOCS.2010.8"},{"key":"21_CR21","doi-asserted-by":"crossref","unstructured":"Druk, E., Ishai, Y.: Linear-time encodable codes meeting the Gilbert-Varshamov bound and their cryptographic applications. In: Proceedings of ITCS 2014, pp. 169\u2013182 (2014)","DOI":"10.1145\/2554797.2554815"},{"key":"21_CR22","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"423","DOI":"10.1007\/978-3-642-55220-5_24","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2014","author":"A Duc","year":"2014","unstructured":"Duc, A., Dziembowski, S., Faust, S.: Unifying leakage models: from probing attacks to noisy leakage. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 423\u2013440. Springer, Heidelberg (2014)"},{"issue":"1","key":"21_CR23","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1002\/(SICI)1098-2418(199808)13:1<1::AID-RSA1>3.0.CO;2-W","volume":"13","author":"G Even","year":"1998","unstructured":"Even, G., Goldreich, O., Luby, M., Nisan, N., Velickovic, B.: Efficient approximation of product distributions. Random Struct. Algorithms 13(1), 1\u201316 (1998)","journal-title":"Random Struct. Algorithms"},{"issue":"5","key":"21_CR24","doi-asserted-by":"publisher","first-page":"1699","DOI":"10.1137\/120897432","volume":"43","author":"J H\u00e5stad","year":"2014","unstructured":"H\u00e5stad, J.: On the correlation of parity and small-depth circuits. SIAM J. Comput. 43(5), 1699\u20131708 (2014)","journal-title":"SIAM J. Comput."},{"key":"21_CR25","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"576","DOI":"10.1007\/978-3-642-39206-1_49","volume-title":"Automata, Languages, and Programming","author":"Y Ishai","year":"2013","unstructured":"Ishai, Y., Kushilevitz, E., Li, X., Ostrovsky, R., Prabhakaran, M., Sahai, A., Zuckerman, D.: Robust pseudorandom generators. In: Fomin, F.V., Freivalds, R., Kwiatkowska, M., Peleg, D. (eds.) ICALP 2013, Part I. LNCS, vol. 7965, pp. 576\u2013588. Springer, Heidelberg (2013)"},{"key":"21_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"406","DOI":"10.1007\/978-3-642-20465-4_23","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2011","author":"Y Ishai","year":"2011","unstructured":"Ishai, Y., Kushilevitz, E., Ostrovsky, R., Prabhakaran, M., Sahai, A.: Efficient non-interactive secure computation. In: Paterson, K.G. (ed.) EUROCRYPT 2011. LNCS, vol. 6632, pp. 406\u2013425. Springer, Heidelberg (2011)"},{"key":"21_CR27","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"607","DOI":"10.1007\/978-3-642-40328-6_42","volume-title":"Approximation, Randomization, and Combinatorial Optimization","author":"Y Ishai","year":"2013","unstructured":"Ishai, Y., Sahai, A., Viderman, M., Weiss, M.: Zero knowledge LTCs and their applications. In: Raghavendra, P., Raskhodnikova, S., Jansen, K., Rolim, J.D.P. (eds.) RANDOM 2013 and APPROX 2013. LNCS, vol. 8096, pp. 607\u2013622. Springer, Heidelberg (2013)"},{"key":"21_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/978-3-540-45146-4_27","volume-title":"Advances in Cryptology - CRYPTO 2003","author":"Y Ishai","year":"2003","unstructured":"Ishai, Y., Sahai, A., Wagner, D.: Private circuits: securing hardware against probing attacks. In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 463\u2013481. Springer, Heidelberg (2003)"},{"issue":"4","key":"21_CR29","doi-asserted-by":"publisher","first-page":"465","DOI":"10.1007\/BF01271266","volume":"16","author":"J Kahn","year":"1996","unstructured":"Kahn, J., Linial, N., Samorodnitsky, A.: Inclusion-exclusion: exact and approximate. Combinatorica 16(4), 465\u2013477 (1996)","journal-title":"Combinatorica"},{"issue":"3","key":"21_CR30","doi-asserted-by":"publisher","first-page":"285","DOI":"10.1017\/S096354830200559X","volume":"12","author":"M Krause","year":"2003","unstructured":"Krause, M., Simon, H.: Determining the optimal contrast for secret sharing schemes in visual cryptography. Comb. Probab. Comput. 12(3), 285\u2013299 (2003)","journal-title":"Comb. Probab. Comput."},{"issue":"10","key":"21_CR31","first-page":"2172","volume":"82","author":"H Kuwakado","year":"1999","unstructured":"Kuwakado, H., Tanaka, H.: Image size invariant visual cryptography. IEICE Trans. Fundam. Electron. Commun. Comput. Sci. 82(10), 2172\u20132177 (1999)","journal-title":"IEICE Trans. Fundam. Electron. Commun. Comput. Sci."},{"issue":"4","key":"21_CR32","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1007\/BF02128670","volume":"10","author":"N Linial","year":"1990","unstructured":"Linial, N., Nisan, N.: Approximate inclusion-exclusion. Combinatorica 10(4), 349\u2013365 (1990)","journal-title":"Combinatorica"},{"key":"21_CR33","volume-title":"Perceptrons","author":"M Minsky","year":"1969","unstructured":"Minsky, M., Papert, S.: Perceptrons. MIT Press, Cambridge (1969)"},{"key":"21_CR34","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/BFb0053419","volume-title":"Advances in Cryptology - EUROCRYPT \u201994","author":"M Naor","year":"1995","unstructured":"Naor, M., Shamir, A.: Visual cryptography. In: De Santis, A. (ed.) EUROCRYPT 1994. LNCS, vol. 950, pp. 1\u201312. Springer, Heidelberg (1995)"},{"key":"21_CR35","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/BF01263419","volume":"4","author":"N Nisan","year":"1994","unstructured":"Nisan, N., Szegedy, M.: On the degree of Boolean functions as real polynomials. Comput. Complex. 4, 301\u2013313 (1994)","journal-title":"Comput. Complex."},{"key":"21_CR36","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781139814782","volume-title":"Analysis of Boolean Functions","author":"R O\u2019Donnell","year":"2014","unstructured":"O\u2019Donnell, R.: Analysis of Boolean Functions. Cambridge University Press, Cambridge (2014)"},{"issue":"3","key":"21_CR37","doi-asserted-by":"publisher","first-page":"327","DOI":"10.1007\/s00493-010-2173-3","volume":"30","author":"R O\u2019Donnell","year":"2010","unstructured":"O\u2019Donnell, R., Servedio, R.A.: New degree bounds for polynomial threshold functions. Combinatorica 30(3), 327\u2013358 (2010)","journal-title":"Combinatorica"},{"key":"21_CR38","doi-asserted-by":"crossref","unstructured":"Paturi, R.: On the degree of polynomials that approximate symmetric boolean functions (preliminary version). In: Proceedings of STOC 1992, pp. 468\u2013474 (1992)","DOI":"10.1145\/129712.129758"},{"issue":"5","key":"21_CR39","doi-asserted-by":"publisher","first-page":"3038","DOI":"10.1109\/TIT.2013.2237944","volume":"59","author":"H Randriambololona","year":"2013","unstructured":"Randriambololona, H.: Asymptotically good binary linear codes with asymptotically good self-intersection spans. IEEE Trans. Inf. Theor. 59(5), 3038\u20133045 (2013)","journal-title":"IEEE Trans. Inf. Theor."},{"issue":"1","key":"21_CR40","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1145\/1490270.1490273","volume":"1","author":"AA Razborov","year":"2009","unstructured":"Razborov, A.A.: A simple proof of Bazzi\u2019s theorem. ACM Trans. Comput. Theor. (TOCT) 1(1), 1\u20134 (2009)","journal-title":"ACM Trans. Comput. Theor. (TOCT)"},{"issue":"11","key":"21_CR41","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":"6","key":"21_CR42","doi-asserted-by":"publisher","first-page":"1969","DOI":"10.1137\/080733644","volume":"40","author":"AA Sherstov","year":"2011","unstructured":"Sherstov, A.A.: The pattern matrix method. SIAM J. Comput. 40(6), 1969\u20132000 (2011)","journal-title":"SIAM J. Comput."},{"key":"21_CR43","doi-asserted-by":"crossref","unstructured":"Sherstov, A.A.: The power of asymmetry in constant-depth circuits. In: Proceedings of FOCS 2015 (2015)","DOI":"10.1109\/FOCS.2015.34"},{"key":"21_CR44","unstructured":"Spalek, R.: A dual polynomial for OR (2008). CoRR, abs\/0803.4516"},{"key":"21_CR45","unstructured":"Tal, A.: Tight bounds on The Fourier Spectrum of AC$$^0$$. Electronic Colloquium on Computational Complexity, Technical report TR14-174 (2014). \n                      www.eccc.uni-trier.de\/"},{"issue":"3","key":"21_CR46","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\u2013375 (2009)","journal-title":"Comput. Complex."},{"issue":"1","key":"21_CR47","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(1), 191\u2013218 (2012)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"21_CR48","doi-asserted-by":"publisher","first-page":"103","DOI":"10.4086\/toc.2007.v003a006","volume":"3","author":"D Zuckerman","year":"2007","unstructured":"Zuckerman, D.: Linear degree extractors and the inapproximability of max clique and chromatic number. Theor. Comput. 3(1), 103\u2013128 (2007)","journal-title":"Theor. Comput."}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 CRYPTO 2016"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-662-53015-3_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,7,20]],"date-time":"2020-07-20T00:07:56Z","timestamp":1595203676000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53015-3_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662530146","9783662530153"],"references-count":48,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53015-3_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"21 July 2016","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","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":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14 August 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"18 August 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"36","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"crypto2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}