{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,3,25]],"date-time":"2025-03-25T14:35:18Z","timestamp":1742913318843,"version":"3.40.3"},"publisher-location":"Cham","reference-count":46,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319446172"},{"type":"electronic","value":"9783319446189"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"unspecified","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-44618-9_27","type":"book-chapter","created":{"date-parts":[[2016,8,10]],"date-time":"2016-08-10T01:10:01Z","timestamp":1470791401000},"page":"509-528","source":"Crossref","is-referenced-by-count":6,"title":["Secret Sharing Schemes for Dense Forbidden Graphs"],"prefix":"10.1007","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[]},{"given":"Oriol","family":"Farr\u00e0s","sequence":"additional","affiliation":[]},{"given":"Naty","family":"Peter","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2016,8,11]]},"reference":[{"issue":"3","key":"27_CR1","doi-asserted-by":"crossref","first-page":"201","DOI":"10.1007\/BF02579381","volume":"6","author":"N Alon","year":"1986","unstructured":"Alon, N.: Covering graphs by the minimum number of equivalence relations. Combinatorica 6(3), 201\u2013206 (1986)","journal-title":"Combinatorica"},{"issue":"3","key":"27_CR2","doi-asserted-by":"crossref","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":"27_CR3","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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":"27_CR4","doi-asserted-by":"crossref","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."},{"issue":"2","key":"27_CR5","doi-asserted-by":"crossref","first-page":"336","DOI":"10.1007\/s00145-014-9195-8","volume":"29","author":"A Beimel","year":"2016","unstructured":"Beimel, A., Farr\u00e0s, O., Mintz, Y.: Secret-sharing schemes for very dense graphs. J. Cryptol. 29(2), 336\u2013362 (2016)","journal-title":"J. Cryptol."},{"issue":"1","key":"27_CR6","doi-asserted-by":"crossref","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":"27_CR7","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"key":"27_CR8","doi-asserted-by":"crossref","unstructured":"Ben-Or, M., Goldwasser, S., Wigderson, A.: Completeness theorems for noncryptographic fault-tolerant distributed computations. In: Proceedings of the 20th ACM Symposium on the Theory of Computing, pp. 1\u201310 (1988)","DOI":"10.1145\/62212.62213"},{"key":"27_CR9","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"27","DOI":"10.1007\/0-387-34799-2_3","volume-title":"Advances in Cryptology - CRYPTO 1988","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":"27_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"67","DOI":"10.1007\/3-540-57220-1_53","volume-title":"Advances in Cryptology - AUSCRYPT 1992","author":"M Bertilsson","year":"1993","unstructured":"Bertilsson, M., Ingemarsson, I.: A construction of practical secret sharing schemes using linear block codes. In: Zheng, Y., Seberry, J. (eds.) AUSCRYPT 1992. LNCS, vol. 718, pp. 67\u201379. Springer, Heidelberg (1993)"},{"key":"27_CR11","doi-asserted-by":"crossref","unstructured":"Blakley, G.R.: Safeguarding cryptographic keys. In: Proceedings of the 1979 AFIPS National Computer Conference, AFIPS Conference proceedings, vol. 48, pp. 313\u2013317. AFIPS Press (1979)","DOI":"10.1109\/MARK.1979.8817296"},{"issue":"2","key":"27_CR12","doi-asserted-by":"crossref","first-page":"107","DOI":"10.1023\/A:1008216403325","volume":"11","author":"C Blundo","year":"1997","unstructured":"Blundo, C., De Santis, A., de Simone, R., Vaccaro, U.: Tight bounds on the information rate of secret sharing schemes. Des. Codes Crypt. 11(2), 107\u2013122 (1997)","journal-title":"Des. Codes Crypt."},{"issue":"1","key":"27_CR13","doi-asserted-by":"crossref","first-page":"39","DOI":"10.1007\/BF00204801","volume":"8","author":"C Blundo","year":"1995","unstructured":"Blundo, C., De Santis, A., Stinson, D.R., Vaccaro, U.: Graph decomposition and secret sharing schemes. J. Cryptol. 8(1), 39\u201364 (1995)","journal-title":"J. Cryptol."},{"key":"27_CR14","first-page":"105","volume":"6","author":"EF Brickell","year":"1989","unstructured":"Brickell, E.F.: Some ideal secret sharing schemes. J. Combin. Math. Combin. Comput. 6, 105\u2013113 (1989)","journal-title":"J. Combin. Math. Combin. Comput."},{"issue":"73","key":"27_CR15","doi-asserted-by":"crossref","first-page":"123","DOI":"10.1007\/BF00196772","volume":"4","author":"EF Brickell","year":"1991","unstructured":"Brickell, E.F., Davenport, D.M.: On the classification of ideal secret sharing schemes. J. Cryptol. 4(73), 123\u2013134 (1991)","journal-title":"J. Cryptol."},{"issue":"6","key":"27_CR16","doi-asserted-by":"crossref","first-page":"689","DOI":"10.1007\/BF00264314","volume":"23","author":"S Bublitz","year":"1986","unstructured":"Bublitz, S.: Decomposition of graphs and monotone formula size of homogeneous functions. Acta Inf. 23(6), 689\u2013696 (1986)","journal-title":"Acta Inf."},{"issue":"3","key":"27_CR17","doi-asserted-by":"crossref","first-page":"157","DOI":"10.1007\/BF00198463","volume":"6","author":"RM Capocelli","year":"1993","unstructured":"Capocelli, R.M., De Santis, A., Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. J. Cryptol. 6(3), 157\u2013168 (1993)","journal-title":"J. Cryptol."},{"key":"27_CR18","doi-asserted-by":"crossref","unstructured":"Chaum, D., Cr\u00e9peau, C., Damg\u00e5rd, I.: Multiparty unconditionally secure protocols. In: Proceedings of the 20th ACM Symposium on the Theory of Computing, pp. 11\u201319 (1988)","DOI":"10.1145\/62212.62214"},{"issue":"2","key":"27_CR19","doi-asserted-by":"crossref","first-page":"87","DOI":"10.1007\/BF02620136","volume":"6","author":"B Chor","year":"1993","unstructured":"Chor, B., Kushilevitz, E.: Secret sharing over infinite domains. J. Cryptol. 6(2), 87\u201396 (1993)","journal-title":"J. Cryptol."},{"key":"27_CR20","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). www.eccc.uni-trier.de\/eccc\/","journal-title":"Electron. Colloq. Comput. Complex."},{"issue":"3\u20134","key":"27_CR21","first-page":"429","volume":"32","author":"L Csirmaz","year":"1996","unstructured":"Csirmaz, L.: The dealer\u2019s random bits in perfect secret sharing schemes. Studia Sci. Math. Hungar. 32(3\u20134), 429\u2013437 (1996)","journal-title":"Studia Sci. Math. Hungar."},{"issue":"4","key":"27_CR22","doi-asserted-by":"crossref","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":"27_CR23","unstructured":"Csirmaz, L.: Secret sharing schemes on graphs. Technical report 2005\/059, Cryptology ePrint Archive (2005). eprint.iacr.org\/"},{"key":"27_CR24","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/3-540-46766-1_37","volume-title":"Advances in Cryptology - CRYPTO 1991","author":"YG Desmedt","year":"1992","unstructured":"Desmedt, Y.G., Frankel, Y.: Shared generation of authenticators and signatures. In: Feigenbaum, J. (ed.) CRYPTO 1991. LNCS, vol. 576, pp. 457\u2013469. Springer, Heidelberg (1992)"},{"issue":"2","key":"27_CR25","doi-asserted-by":"crossref","first-page":"143","DOI":"10.1007\/BF01398012","volume":"6","author":"M Dijk van","year":"1995","unstructured":"van Dijk, M.: On the information rate of perfect secret sharing schemes. Des. Codes Crypt. 6(2), 143\u2013169 (1995)","journal-title":"Des. Codes Crypt."},{"issue":"1\u20133","key":"27_CR26","doi-asserted-by":"crossref","first-page":"249","DOI":"10.1016\/S0012-365X(96)00124-0","volume":"170","author":"P Erd\u00f6s","year":"1997","unstructured":"Erd\u00f6s, P., Pyber, L.: Covering a graph by complete bipartite graphs. Discrete Math. 170(1\u20133), 249\u2013251 (1997)","journal-title":"Discrete Math."},{"key":"27_CR27","doi-asserted-by":"crossref","unstructured":"G\u00e1l, A.: A characterization of span program size and improved lower bounds for monotone span programs. In: Proceedings of the 30th ACM Symposium on the Theory of Computing, pp. 429\u2013437 (1998)","DOI":"10.1145\/276698.276855"},{"key":"27_CR28","doi-asserted-by":"crossref","first-page":"321","DOI":"10.1016\/S0020-0190(03)00334-X","volume":"87","author":"A G\u00e1l","year":"2003","unstructured":"G\u00e1l, A., Pudl\u00e1k, P.: Monotone complexity and the rank of matrices. Inform. Process. Lett. 87, 321\u2013326 (2003)","journal-title":"Inform. Process. Lett."},{"key":"27_CR29","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","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)"},{"issue":"3","key":"27_CR30","doi-asserted-by":"crossref","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":"27_CR31","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: Proceedings of the 13th ACM conference on Computer and Communications Security, pp. 89\u201398 (2006)","DOI":"10.1145\/1180405.1180418"},{"key":"27_CR32","doi-asserted-by":"crossref","unstructured":"Ito, M., Saito, A., Nishizeki, T.: Secret sharing schemes realizing general access structure. In: Proceedings of the IEEE Global Telecommunication Conference, Globecom, vol. 87, pp. 99\u2013102 (1987). Journal version: Multiple assignment scheme for sharing secret. J. Cryptol. 6(1), 15\u201320 (1993)","DOI":"10.1007\/BF02620229"},{"issue":"1","key":"27_CR33","doi-asserted-by":"crossref","first-page":"55","DOI":"10.1002\/jgt.20367","volume":"61","author":"S Jukna","year":"2009","unstructured":"Jukna, S.: On set intersection representations of graphs. J. Graph Theor. 61(1), 55\u201375 (2009)","journal-title":"J. Graph Theor."},{"key":"27_CR34","doi-asserted-by":"crossref","unstructured":"Karchmer, M., Wigderson, A.: On span programs. In: Proceedings of the 8th IEEE Structure in Complexity Theory, pp. 102\u2013111 (1993)","DOI":"10.1109\/SCT.1993.336536"},{"key":"27_CR35","unstructured":"Mart\u00ed-Farr\u00e9, J., Padr\u00f3, C.: Secret sharing schemes on sparse homogeneous access structures with rank three. Electr. J. Comb. 11(1) (2004). http:\/\/www.combinatorics.org\/ojs\/index.php\/eljc\/article\/view\/v11i1r72\/"},{"issue":"2","key":"27_CR36","doi-asserted-by":"crossref","first-page":"95","DOI":"10.1515\/jmc.2010.004","volume":"4","author":"J Mart\u00ed-Farr\u00e9","year":"2010","unstructured":"Mart\u00ed-Farr\u00e9, J., Padr\u00f3, C.: On secret sharing schemes, matroids and polymatroids. J. Math. Cryptol. 4(2), 95\u2013120 (2010)","journal-title":"J. Math. Cryptol."},{"key":"27_CR37","unstructured":"Mintz, Y.: Information ratios of graph secret-sharing schemes. Master\u2019s thesis, Department of Computer Science, Ben Gurion University (2012)"},{"key":"27_CR38","doi-asserted-by":"crossref","unstructured":"Naor, M., Wool, A.: Access control and signatures via quorum secret sharing. In: 3rd ACM Conference on Computer and Communications Security, pp. 157\u2013167 (1996)","DOI":"10.1145\/238168.238209"},{"issue":"6","key":"27_CR39","doi-asserted-by":"crossref","first-page":"345","DOI":"10.1016\/S0020-0190(02)00213-2","volume":"83","author":"C Padr\u00f3","year":"2002","unstructured":"Padr\u00f3, C., S\u00e1ez, G.: Lower bounds on the information rate of secret sharing schemes with homogeneous access structure. Inform. Process. Lett. 83(6), 345\u2013351 (2002)","journal-title":"Inform. Process. Lett."},{"key":"27_CR40","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"457","DOI":"10.1007\/11426639_27","volume-title":"Advances in Cryptology \u2013 EUROCRYPT 2005","author":"A Sahai","year":"2005","unstructured":"Sahai, A., Waters, B.: Fuzzy identity-based encryption. In: Cramer, R. (ed.) EUROCRYPT 2005. LNCS, vol. 3494, pp. 457\u2013473. Springer, Heidelberg (2005)"},{"key":"27_CR41","doi-asserted-by":"crossref","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, 612\u2013613 (1979)","journal-title":"Commun. ACM"},{"key":"27_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"304","DOI":"10.1007\/978-3-540-77444-0_31","volume-title":"Distributed Computing and Networking","author":"B Shankar","year":"2008","unstructured":"Shankar, B., Srinathan, K., Rangan, C.P.: Alternative protocols for generalized oblivious transfer. In: Rao, S., Chatterjee, M., Jayanti, P., Murthy, C.S.R., Saha, S.K. (eds.) ICDCN 2008. LNCS, vol. 4904, pp. 304\u2013309. Springer, Heidelberg (2008)"},{"issue":"1","key":"27_CR43","doi-asserted-by":"crossref","first-page":"118","DOI":"10.1109\/18.272461","volume":"40","author":"DR Stinson","year":"1994","unstructured":"Stinson, D.R.: Decomposition construction for secret sharing schemes. IEEE Trans. Inf. Theor. 40(1), 118\u2013125 (1994)","journal-title":"IEEE Trans. Inf. Theor."},{"key":"27_CR44","unstructured":"Sun, H., Shieh, S.: Secret sharing in graph-based prohibited structures. In: Proceedings IEEE INFOCOM 1997, pp. 718\u2013724 (1997)"},{"issue":"1","key":"27_CR45","doi-asserted-by":"crossref","first-page":"11","DOI":"10.1007\/s10623-010-9378-8","volume":"58","author":"T Tassa","year":"2011","unstructured":"Tassa, T.: Generalized oblivious transfer by secret sharing. Des. Codes Crypt. 58(1), 11\u201321 (2011)","journal-title":"Des. Codes Crypt."},{"key":"27_CR46","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"crossref","first-page":"53","DOI":"10.1007\/978-3-642-19379-8_4","volume-title":"Public Key Cryptography \u2013 PKC 2011","author":"B Waters","year":"2011","unstructured":"Waters, B.: Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 53\u201370. Springer, Heidelberg (2011)"}],"container-title":["Lecture Notes in Computer Science","Security and Cryptography for Networks"],"original-title":[],"link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-44618-9_27","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2020,9,24]],"date-time":"2020-09-24T23:55:20Z","timestamp":1600991720000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-44618-9_27"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319446172","9783319446189"],"references-count":46,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-44618-9_27","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]}}}