{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,28]],"date-time":"2026-02-28T13:01:31Z","timestamp":1772283691306,"version":"3.50.1"},"publisher-location":"Berlin, Heidelberg","reference-count":31,"publisher":"Springer Berlin Heidelberg","isbn-type":[{"value":"9783662536438","type":"print"},{"value":"9783662536445","type":"electronic"}],"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-53644-5_18","type":"book-chapter","created":{"date-parts":[[2016,10,20]],"date-time":"2016-10-20T03:24:08Z","timestamp":1476933848000},"page":"471-484","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":16,"title":["Threshold Secret Sharing Requires a Linear Size Alphabet"],"prefix":"10.1007","author":[{"given":"Andrej","family":"Bogdanov","sequence":"first","affiliation":[]},{"given":"Siyao","family":"Guo","sequence":"additional","affiliation":[]},{"given":"Ilan","family":"Komargodski","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,10,21]]},"reference":[{"issue":"3","key":"18_CR1","doi-asserted-by":"publisher","first-page":"301","DOI":"10.1007\/s004930050058","volume":"19","author":"L Babai","year":"1999","unstructured":"Babai, L., G\u00e1l, A., Wigderson, A.: Superpolynomial lower bounds for monotone span programs. Combinatorica 19(3), 301\u2013319 (1999)","journal-title":"Combinatorica"},{"key":"18_CR2","unstructured":"Beimel, A.: Secure schemes for secret sharing and key distribution. Ph.D. thesis, Technion - Israel Institute of Technology (1996)"},{"key":"18_CR3","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., Guo, Z., Ling, S., Shao, F., Tang, Y., Wang, H., Xing, C. (eds.) IWCC 2011. LNCS, vol. 6639, pp. 11\u201346. Springer, Heidelberg (2011)"},{"issue":"3","key":"18_CR4","doi-asserted-by":"publisher","first-page":"786","DOI":"10.1109\/18.335890","volume":"40","author":"A Beimel","year":"1994","unstructured":"Beimel, A., Chor, B.: Universally ideal secret-sharing schemes. IEEE Trans. Inf. Theor. 40(3), 786\u2013794 (1994)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"18_CR5","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"253","DOI":"10.1007\/978-3-540-70936-7_14","volume-title":"Theory of Cryptography","author":"A Beimel","year":"2007","unstructured":"Beimel, A., Franklin, M.K.: Weakly-private secret sharing schemes. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 253\u2013272. Springer, Heidelberg (2007)"},{"issue":"1","key":"18_CR6","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1007\/BF01202040","volume":"6","author":"A Beimel","year":"1997","unstructured":"Beimel, A., G\u00e1l, A., Paterson, M.: Lower bounds for monotone span programs. Comput. Complex. 6(1), 29\u201345 (1997)","journal-title":"Comput. Complex."},{"key":"18_CR7","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y.: On the power of nonlinear secrect-sharing. In: 16th Annual IEEE Conference on Computational Complexity, CCC, pp. 188\u2013202 (2001)","DOI":"10.1109\/CCC.2001.933886"},{"issue":"9","key":"18_CR8","doi-asserted-by":"publisher","first-page":"5634","DOI":"10.1109\/TIT.2011.2162183","volume":"57","author":"A Beimel","year":"2011","unstructured":"Beimel, A., Orlov, I.: Secret sharing and non-shannon information inequalities. IEEE Trans. Inf. Theor. 57(9), 5634\u20135649 (2011)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"18_CR9","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 - CRYPTO \u201988","author":"JC Benaloh","year":"1990","unstructured":"Benaloh, J.C., Leichter, J.: Generalized secret sharing and monotone functions. In: Goldwasser, S. (ed.) CRYPTO 1988. LNCS, vol. 403, pp. 27\u201335. Springer, Heidelberg (1990)"},{"key":"18_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"242","DOI":"10.1007\/3-540-39568-7_20","volume-title":"Advances in Cryptology","author":"GR Blakley","year":"1985","unstructured":"Blakley, G.R., Meadows, C.: Security of ramp schemes. In: Blakely, G.R., Chaum, D. (eds.) CRYPTO 1984. LNCS, vol. 196, pp. 242\u2013268. Springer, Heidelberg (1985)"},{"key":"18_CR11","first-page":"313","volume":"22","author":"GR Blakley","year":"1979","unstructured":"Blakley, G.R.: Safeguarding cryptographic keys. Proc. AFIPS Natl. Comput. Conf. 22, 313\u2013317 (1979)","journal-title":"Proc. AFIPS Natl. Comput. Conf."},{"key":"18_CR12","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). doi: 10.1007\/978-3-662-53015-3_21"},{"issue":"3","key":"18_CR13","doi-asserted-by":"publisher","first-page":"157","DOI":"10.1007\/BF00198463","volume":"6","author":"RM Capocelli","year":"1993","unstructured":"Capocelli, R.M., Santis, A.D., Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. J. Cryptol. 6(3), 157\u2013167 (1993)","journal-title":"J. Cryptol."},{"issue":"9","key":"18_CR14","doi-asserted-by":"publisher","first-page":"5600","DOI":"10.1109\/TIT.2013.2264504","volume":"59","author":"I Cascudo Pueyo","year":"2013","unstructured":"Cascudo Pueyo, I., Cramer, R., Xing, C.: Bounds on the threshold gap in secret sharing and its applications. IEEE Trans. Inf. Theor. 59(9), 5600\u20135612 (2013)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"18_CR15","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"521","DOI":"10.1007\/11818175_31","volume-title":"Advances in Cryptology - CRYPTO 2006","author":"H Chen","year":"2006","unstructured":"Chen, H., Cramer, R.: Algebraic geometric secret sharing schemes and secure multi-party computations over small fields. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 521\u2013536. Springer, Heidelberg (2006)"},{"key":"18_CR16","first-page":"64","volume":"23","author":"SA Cook","year":"2016","unstructured":"Cook, S.A., Pitassi, T., Robere, R., Rossman, B.: Exponential lower bounds for monotone span programs. Electron. Colloq. Comput. Complex. 23, 64 (2016)","journal-title":"Electron. Colloq. Comput. Complex."},{"key":"18_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9781107337756","volume-title":"Secure Multiparty Computation and Secret Sharing","author":"R Cramer","year":"2015","unstructured":"Cramer, R., Damg\u00e5rd, I., Nielsen, J.B.: Secure Multiparty Computation and Secret Sharing. Cambridge University Press, Cambridge (2015)"},{"key":"18_CR18","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"344","DOI":"10.1007\/11535218_21","volume-title":"Advances in Cryptology \u2013 CRYPTO 2005","author":"R Cramer","year":"2005","unstructured":"Cramer, R., Fehr, S., Stam, M.: Black-box secret sharing from primitive sets in algebraic number fields. In: Shoup, V. (ed.) CRYPTO 2005. LNCS, vol. 3621, pp. 344\u2013360. Springer, Heidelberg (2005)"},{"issue":"4","key":"18_CR19","doi-asserted-by":"publisher","first-page":"223","DOI":"10.1007\/s001459900029","volume":"10","author":"L Csirmaz","year":"1997","unstructured":"Csirmaz, L.: The size of a share must be large. J. Cryptol. 10(4), 223\u2013231 (1997)","journal-title":"J. Cryptol."},{"key":"18_CR20","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"217","DOI":"10.1007\/978-3-662-44381-1_13","volume-title":"Advances in Cryptology \u2013 CRYPTO 2014","author":"O Farr\u00e0s","year":"2014","unstructured":"Farr\u00e0s, O., Hansen, T., Kaced, T., Padr\u00f3, C.: Optimal non-perfect uniform secret sharing schemes. In: Garay, J.A., Gennaro, R. (eds.) CRYPTO 2014, Part II. LNCS, vol. 8617, pp. 217\u2013234. Springer, Heidelberg (2014)"},{"key":"18_CR21","unstructured":"Farr\u00e0s, O., Mollev\u00ed, S.M., Padr\u00f3, C.: A note on non-perfect secret sharing. IACR Cryptology ePrint Archive, p. 348 (2016)"},{"issue":"4","key":"18_CR22","doi-asserted-by":"publisher","first-page":"277","DOI":"10.1007\/s000370100001","volume":"10","author":"A G\u00e1l","year":"2001","unstructured":"G\u00e1l, A.: A characterization of span program size and improved lower bounds for monotone span programs. Comput. Complex. 10(4), 277\u2013296 (2001)","journal-title":"Comput. Complex."},{"issue":"1","key":"18_CR23","doi-asserted-by":"publisher","first-page":"15","DOI":"10.1007\/BF02620229","volume":"6","author":"M Ito","year":"1993","unstructured":"Ito, M., Saito, A., Nishizeki, T.: Multiple assignment scheme for sharing secret. J. Cryptol. 6(1), 15\u201320 (1993)","journal-title":"J. Cryptol."},{"key":"18_CR24","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: 8th Annual Structure in Complexity Theory Conference, pp. 102\u2013111 (1993)","DOI":"10.1109\/SCT.1993.336536"},{"key":"18_CR25","unstructured":"Kilian, J., Nisan, N.: Unpublished (1990). Referenced in [4,2,5,14]"},{"key":"18_CR26","doi-asserted-by":"crossref","unstructured":"Komargodski, I., Naor, M., Yogev, E.: How to share a secret, infinitely. IACR Cryptology ePrint Archive 2016, 194 (2016)","DOI":"10.1007\/978-3-662-53644-5_19"},{"key":"18_CR27","doi-asserted-by":"publisher","first-page":"65","DOI":"10.1007\/s12095-010-0039-6","volume":"3","author":"KM Martin","year":"2011","unstructured":"Martin, K.M., Paterson, M.B., Stinson, D.R.: Error decodable secret sharing and one-round perfectly secure message transmission for general adversary structures. Crypt. Commun. 3, 65\u201386 (2011)","journal-title":"Crypt. Commun."},{"issue":"1","key":"18_CR28","doi-asserted-by":"publisher","first-page":"599","DOI":"10.1109\/TIT.2015.2500232","volume":"62","author":"SM Mollev\u00ed","year":"2016","unstructured":"Mollev\u00ed, S.M., Padr\u00f3, C., Yang, A.: Secret sharing, rank inequalities, and information inequalities. IEEE Trans. Inf. Theor. 62(1), 599\u2013609 (2016)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"18_CR29","doi-asserted-by":"publisher","first-page":"229","DOI":"10.1007\/s12095-013-0082-1","volume":"5","author":"MB Paterson","year":"2013","unstructured":"Paterson, M.B., Stinson, D.R.: A simple combinatorial treatment of constructions and threshold gaps of ramp schemes. Crypt. Commun. 5, 229\u2013240 (2013)","journal-title":"Crypt. Commun."},{"issue":"11","key":"18_CR30","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"},{"key":"18_CR31","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1016\/S0020-0190(98)00204-X","volume":"69","author":"DR Stinson","year":"1999","unstructured":"Stinson, D.R., Wei, R.: An application of ramp schemes to broadcast encryption. Inf. Process. Lett. 69, 131\u2013135 (1999)","journal-title":"Inf. Process. Lett."}],"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-662-53644-5_18","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T18:03:36Z","timestamp":1749665016000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-662-53644-5_18"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783662536438","9783662536445"],"references-count":31,"URL":"https:\/\/doi.org\/10.1007\/978-3-662-53644-5_18","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"21 October 2016","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":"Beijing","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"China","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":"1 November 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 November 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"14","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"tcc2016","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"}]}}