{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,5,6]],"date-time":"2026-05-06T10:52:42Z","timestamp":1778064762848,"version":"3.51.4"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer International Publishing","isbn-type":[{"value":"9783319783802","type":"print"},{"value":"9783319783819","type":"electronic"}],"license":[{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2018,1,1]],"date-time":"2018-01-01T00:00:00Z","timestamp":1514764800000},"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":[[2018]]},"DOI":"10.1007\/978-3-319-78381-9_21","type":"book-chapter","created":{"date-parts":[[2018,3,30]],"date-time":"2018-03-30T05:53:14Z","timestamp":1522389194000},"page":"567-596","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":35,"title":["Towards Breaking the Exponential Barrier for General Secret Sharing"],"prefix":"10.1007","author":[{"given":"Tianren","family":"Liu","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vinod","family":"Vaikuntanathan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hoeteck","family":"Wee","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2018,3,31]]},"reference":[{"key":"21_CR1","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1007\/BF01263424","volume":"4","author":"DAM Barrington","year":"1994","unstructured":"Barrington, D.A.M., Beigel, R., Rudich, S.: Representing boolean functions as polynomials modulo composite numbers. Comput. Complex. 4, 367\u2013382 (1994)","journal-title":"Comput. Complex."},{"key":"21_CR2","doi-asserted-by":"crossref","unstructured":"Bhowmick, A., Dvir, Z., Lovett, S.: New lower bounds for matching vector codes. CoRR, abs\/1204.1367 (2012)","DOI":"10.1145\/2488608.2488713"},{"key":"21_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). https:\/\/doi.org\/10.1007\/978-3-642-20901-7_2"},{"key":"21_CR4","unstructured":"Babai, L., Frankl, P.: Linear algebra methods in combinatorics (1998)"},{"key":"21_CR5","doi-asserted-by":"crossref","unstructured":"Beimel, A., G\u00e1l, A., Paterson, M.: Lower bounds for monotone span programs. In: FOCS, pp. 674\u2013681 (1995)","DOI":"10.1109\/SFCS.1995.492669"},{"issue":"3","key":"21_CR6","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":"21_CR7","doi-asserted-by":"crossref","unstructured":"Beimel, A., Ishai, Y.: On the power of nonlinear secret-sharing. In: Proceedings of the 16th Annual IEEE Conference on Computational Complexity, Chicago, 18\u201321 June 2001, pp. 188\u2013202. IEEE Computer Society (2001)","DOI":"10.1109\/CCC.2001.933886"},{"key":"21_CR8","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"317","DOI":"10.1007\/978-3-642-54242-8_14","volume-title":"Theory of Cryptography","author":"A Beimel","year":"2014","unstructured":"Beimel, A., Ishai, Y., Kumaresan, R., Kushilevitz, E.: On the cryptographic complexity of the worst functions. In: Lindell, Y. (ed.) TCC 2014. LNCS, vol. 8349, pp. 317\u2013342. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-642-54242-8_14"},{"key":"21_CR9","doi-asserted-by":"crossref","unstructured":"Benaloh, J.C., Leichter, J.: Generalized secret sharing and monotone functions. In: Proceedings of the 8th Annual International Cryptology Conference on Advances in Cryptology, CRYPTO 1988, Santa Barbara, 21\u201325 August 1988, pp. 27\u201335 (1988)","DOI":"10.1007\/0-387-34799-2_3"},{"key":"21_CR10","doi-asserted-by":"crossref","unstructured":"Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of AFIPS 1979 National Computer Conference, pp. 313\u2013317 (1979)","DOI":"10.1109\/MARK.1979.8817296"},{"key":"21_CR11","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"596","DOI":"10.1007\/3-540-39200-9_37","volume-title":"Advances in Cryptology \u2014 EUROCRYPT 2003","author":"R Cramer","year":"2003","unstructured":"Cramer, R., Fehr, S., Ishai, Y., Kushilevitz, E.: Efficient multi-party computation over rings. In: Biham, E. (ed.) EUROCRYPT 2003. LNCS, vol. 2656, pp. 596\u2013613. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/3-540-39200-9_37"},{"issue":"6","key":"21_CR12","doi-asserted-by":"publisher","first-page":"965","DOI":"10.1145\/293347.293350","volume":"45","author":"B Chor","year":"1998","unstructured":"Chor, B., Kushilevitz, E., Goldreich, O., Sudan, M.: Private information retrieval. J. ACM 45(6), 965\u2013981 (1998)","journal-title":"J. ACM"},{"issue":"4","key":"21_CR13","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":"21_CR14","doi-asserted-by":"crossref","unstructured":"Dvir, Z., Gopi, S.: 2-server PIR with sub-polynomial communication. In: STOC, pp. 577\u2013584 (2015)","DOI":"10.1145\/2746539.2746546"},{"issue":"4","key":"21_CR15","doi-asserted-by":"publisher","first-page":"1154","DOI":"10.1137\/100804322","volume":"40","author":"Z Dvir","year":"2011","unstructured":"Dvir, Z., Gopalan, P., Yekhanin, S.: Matching vector codes. SIAM J. Comput. 40(4), 1154\u20131178 (2011)","journal-title":"SIAM J. Comput."},{"key":"21_CR16","doi-asserted-by":"crossref","unstructured":"Efremenko, K.: 3-query locally decodable codes of subexponential length, vol. 41, pp. 1694\u20131703 (2012)","DOI":"10.1137\/090772721"},{"key":"21_CR17","doi-asserted-by":"crossref","unstructured":"Feige, U., Kilian, J., Naor, M.: A minimal model for secure computation (extended abstract). In: Leighton, F.T., Goodrich, M.T. (eds.) Proceedings of the Twenty-Sixth Annual ACM Symposium on Theory of Computing, 23\u201325 May 1994, Montr\u00e9al, pp. 554\u2013563. ACM (1994)","DOI":"10.1145\/195058.195408"},{"issue":"3","key":"21_CR18","doi-asserted-by":"publisher","first-page":"592","DOI":"10.1006\/jcss.1999.1689","volume":"60","author":"Y Gertner","year":"2000","unstructured":"Gertner, Y., Ishai, Y., Kushilevitz, E., Malkin, T.: Protecting data privacy in private information retrieval schemes. J. Comput. Syst. Sci. 60(3), 592\u2013629 (2000)","journal-title":"J. Comput. Syst. Sci."},{"key":"21_CR19","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"485","DOI":"10.1007\/978-3-662-48000-7_24","volume-title":"Advances in Cryptology \u2013 CRYPTO 2015","author":"R Gay","year":"2015","unstructured":"Gay, R., Kerenidis, I., Wee, H.: Communication complexity of conditional disclosure of secrets and attribute-based encryption. In: Gennaro, R., Robshaw, M. (eds.) CRYPTO 2015. LNCS, vol. 9216, pp. 485\u2013502. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48000-7_24"},{"key":"21_CR20","doi-asserted-by":"crossref","unstructured":"Goyal, V., Pandey, O., Sahai, A., Waters, B.: Attribute-based encryption for fine-grained access control of encrypted data. In: ACM Conference on Computer and Communications Security, pp. 89\u201398 (2006)","DOI":"10.1145\/1180405.1180418"},{"issue":"1","key":"21_CR21","doi-asserted-by":"publisher","first-page":"71","DOI":"10.1007\/s004930070032","volume":"20","author":"V Grolmusz","year":"2000","unstructured":"Grolmusz, V.: Superpolynomial size set-systems with restricted intersections mod 6 and explicit ramsey graphs. Combinatorica 20(1), 71\u201386 (2000)","journal-title":"Combinatorica"},{"key":"21_CR22","unstructured":"Ishai, Y., Kushilevitz, E.: Private simultaneous messages protocols with applications. In: ISTCS, pp. 174\u2013184 (1997)"},{"key":"21_CR23","doi-asserted-by":"crossref","unstructured":"Ishai, Y., Kushilevitz, E.: Randomizing polynomials: a new representation with applications to round-efficient secure computation. In: 41st Annual Symposium on Foundations of Computer Science, FOCS 2000, 12\u201314 November 2000, Redondo Beach, pp. 294\u2013304. IEEE Computer Society (2000)","DOI":"10.1109\/SFCS.2000.892118"},{"key":"21_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"244","DOI":"10.1007\/3-540-45465-9_22","volume-title":"Automata, Languages and Programming","author":"Y Ishai","year":"2002","unstructured":"Ishai, Y., Kushilevitz, E.: Perfect constant-round secure computation via perfect randomizing polynomials. In: Widmayer, P., Eidenbenz, S., Triguero, F., Morales, R., Conejo, R., Hennessy, M. (eds.) ICALP 2002. LNCS, vol. 2380, pp. 244\u2013256. Springer, Heidelberg (2002). https:\/\/doi.org\/10.1007\/3-540-45465-9_22"},{"issue":"9","key":"21_CR25","doi-asserted-by":"publisher","first-page":"56","DOI":"10.1002\/ecjc.4430720906","volume":"72","author":"M Ito","year":"1989","unstructured":"Ito, M., Saito, A., Nishizeki, T.: Secret sharing scheme realizing general access structure. Electron. Commun. Jpn. (Part III Fundam. Electron. Sci.) 72(9), 56\u201364 (1989)","journal-title":"Electron. Commun. Jpn. (Part III Fundam. Electron. Sci.)"},{"key":"21_CR26","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"650","DOI":"10.1007\/978-3-662-43948-7_54","volume-title":"Automata, Languages, and Programming","author":"Y Ishai","year":"2014","unstructured":"Ishai, Y., Wee, H.: Partial garbling schemes and their applications. In: Esparza, J., Fraigniaud, P., Husfeldt, T., Koutsoupias, E. (eds.) ICALP 2014. LNCS, vol. 8572, pp. 650\u2013662. Springer, Heidelberg (2014). https:\/\/doi.org\/10.1007\/978-3-662-43948-7_54"},{"key":"21_CR27","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: Structure in Complexity Theory Conference, pp. 102\u2013111. IEEE Computer Society (1993)","DOI":"10.1109\/SCT.1993.336536"},{"key":"21_CR28","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"758","DOI":"10.1007\/978-3-319-63688-7_25","volume-title":"Advances in Cryptology \u2013 CRYPTO 2017","author":"T Liu","year":"2017","unstructured":"Liu, T., Vaikuntanathan, V., Wee, H.: Conditional disclosure of secrets via non-linear reconstruction. In: Katz, J., Shacham, H. (eds.) CRYPTO 2017. LNCS, vol. 10401, pp. 758\u2013790. Springer, Cham (2017). https:\/\/doi.org\/10.1007\/978-3-319-63688-7_25"},{"key":"21_CR29","doi-asserted-by":"crossref","unstructured":"Ostrovsky, R., Sahai, A., Waters, B.: Attribute-based encryption with non-monotonic access structures. In: ACM Conference on Computer and Communications Security, pp. 195\u2013203 (2007)","DOI":"10.1145\/1315245.1315270"},{"key":"21_CR30","first-page":"165","volume":"24","author":"T Pitassi","year":"2017","unstructured":"Pitassi, T., Robere, R.: Lifting nullstellensatz to monotone span programs over any field. Electron. Colloq. Comput. Compl. (ECCC) 24, 165 (2017)","journal-title":"Electron. Colloq. Comput. Compl. (ECCC)"},{"key":"21_CR31","doi-asserted-by":"crossref","unstructured":"Robere, R., Pitassi, T., Rossman, B., Cook, S.A.: Exponential lower bounds for monotone span programs. In: FOCS, pp. 406\u2013415 (2016)","DOI":"10.1109\/FOCS.2016.51"},{"issue":"11","key":"21_CR32","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":"21_CR33","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"656","DOI":"10.1007\/978-3-662-48797-6_27","volume-title":"Advances in Cryptology \u2013 ASIACRYPT 2015","author":"V Vaikuntanathan","year":"2015","unstructured":"Vaikuntanathan, V., Vasudevan, P.N.: Secret sharing and statistical zero knowledge. In: Iwata, T., Cheon, J.H. (eds.) ASIACRYPT 2015. LNCS, vol. 9452, pp. 656\u2013680. Springer, Heidelberg (2015). https:\/\/doi.org\/10.1007\/978-3-662-48797-6_27"},{"key":"21_CR34","doi-asserted-by":"crossref","unstructured":"Woodruff, D.P., Yekhanin, S.: A geometric approach to information-theoretic private information retrieval. In: CCC, pp. 275\u2013284 (2005)","DOI":"10.1109\/CCC.2005.2"},{"issue":"1","key":"21_CR35","doi-asserted-by":"publisher","first-page":"1:1","DOI":"10.1145\/1326554.1326555","volume":"55","author":"S Yekhanin","year":"2008","unstructured":"Yekhanin, S.: Towards 3-query locally decodable codes of subexponential length. J. ACM 55(1), 1:1\u20131:16 (2008)","journal-title":"J. ACM"}],"container-title":["Lecture Notes in Computer Science","Advances in Cryptology \u2013 EUROCRYPT 2018"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-78381-9_21","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,7,3]],"date-time":"2025-07-03T03:55:13Z","timestamp":1751514913000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-319-78381-9_21"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018]]},"ISBN":["9783319783802","9783319783819"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-78381-9_21","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018]]},"assertion":[{"value":"31 March 2018","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"EUROCRYPT","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Annual International Conference on the Theory and Applications of Cryptographic Techniques","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Tel Aviv","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Israel","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2018","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"29 April 2018","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"3 May 2018","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"eurocrypt2018","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/eurocrypt.iacr.org\/2018\/index.html","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"}]}}