{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T04:29:40Z","timestamp":1759638580595,"version":"3.40.5"},"reference-count":59,"publisher":"Springer Science and Business Media LLC","issue":"2","license":[{"start":{"date-parts":[[2014,12,24]],"date-time":"2014-12-24T00:00:00Z","timestamp":1419379200000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["J Cryptol"],"published-print":{"date-parts":[[2016,4]]},"DOI":"10.1007\/s00145-014-9195-8","type":"journal-article","created":{"date-parts":[[2014,12,23]],"date-time":"2014-12-23T20:44:19Z","timestamp":1419367459000},"page":"336-362","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":33,"title":["Secret-Sharing Schemes for Very Dense Graphs"],"prefix":"10.1007","volume":"29","author":[{"given":"Amos","family":"Beimel","sequence":"first","affiliation":[]},{"given":"Oriol","family":"Farr\u00e0s","sequence":"additional","affiliation":[]},{"given":"Yuval","family":"Mintz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2014,12,24]]},"reference":[{"key":"9195_CR1","doi-asserted-by":"crossref","unstructured":"N. Alon. Covering graphs by the minimum number of equivalence relations. Combinatorica, 6(3):201\u2013206, 1986.","DOI":"10.1007\/BF02579381"},{"key":"9195_CR2","doi-asserted-by":"crossref","unstructured":"N. Alon and J. H. Spencer. The Probabilistic Method. John Wiley & Sons, 3rd edition, 2008.","DOI":"10.1002\/9780470277331"},{"key":"9195_CR3","doi-asserted-by":"crossref","unstructured":"L. Babai, A. G\u00e1l, and A. Wigderson. Superpolynomial lower bounds for monotone span programs. Combinatorica, 19(3):301\u2013319, 1999.","DOI":"10.1007\/s004930050058"},{"key":"9195_CR4","doi-asserted-by":"crossref","unstructured":"A. Beimel. Secret-sharing schemes: A survey. In IWCC 2011, volume 6639 of Lecture Notes in Computer Science, pages 11\u201346, 2011.","DOI":"10.1007\/978-3-642-20901-7_2"},{"key":"9195_CR5","doi-asserted-by":"crossref","unstructured":"A. Beimel and B. Chor. Universally ideal secret sharing schemes. IEEE Trans. on Information Theory, 40(3):786\u2013794, 1994.","DOI":"10.1109\/18.335890"},{"key":"9195_CR6","doi-asserted-by":"crossref","unstructured":"A. Beimel, A. G\u00e1l, and M. Paterson. Lower bounds for monotone span programs. Computational Complexity, 6(1):29\u201345, 1997. Conference version: FOCS \u201995.","DOI":"10.1007\/BF01202040"},{"key":"9195_CR7","doi-asserted-by":"crossref","unstructured":"A. Beimel, Y. Ishai, R. Kumaresan, and E. Kushilevitz. On the cryptographic complexity of the worst functions. In Y. Lindell, editor, Proc. of the Eleventh Theory of Cryptography Conference\u2013 TCC 2014, volume 8349 of Lecture Notes in Computer Science, pages 317\u2013342. Springer-Verlag, 2014.","DOI":"10.1007\/978-3-642-54242-8_14"},{"key":"9195_CR8","doi-asserted-by":"crossref","unstructured":"M. Ben-Or, S. Goldwasser, and A. Wigderson. Completeness theorems for non cryptographic fault-tolerant distributed computations. In Proc. of the 20th ACM Symp. on the Theory of Computing, pages 1\u201310, 1988.","DOI":"10.1145\/62212.62213"},{"key":"9195_CR9","doi-asserted-by":"crossref","unstructured":"J. Benaloh and J. Leichter. Generalized secret sharing and monotone functions. In S. Goldwasser, editor, Advances in Cryptology \u2013 CRYPTO \u201988, volume 403 of Lecture Notes in Computer Science, pages 27\u201335. Springer-Verlag, 1990.","DOI":"10.1007\/0-387-34799-2_3"},{"key":"9195_CR10","doi-asserted-by":"crossref","unstructured":"G. R. Blakley. Safeguarding cryptographic keys. In R. E. Merwin, J. T. Zanca, and M. Smith, editors, Proc. of the 1979 AFIPS National Computer Conference, volume 48 of AFIPS Conference proceedings, pages 313\u2013317. AFIPS Press, 1979.","DOI":"10.1109\/MARK.1979.8817296"},{"key":"9195_CR11","doi-asserted-by":"crossref","unstructured":"G. R. Blakley and C. Meadows. The security of ramp schemes. In G. R. Blakley and D. Chaum, editors, Advances in Cryptology \u2013 CRYPTO \u201984, volume 196 of Lecture Notes in Computer Science, pages 242\u2013268. Springer-Verlag, 1985.","DOI":"10.1007\/3-540-39568-7_20"},{"key":"9195_CR12","doi-asserted-by":"crossref","unstructured":"C. Blundo, A. De Santis, R. de Simone, and U. Vaccaro. Tight bounds on the information rate of secret sharing schemes. Designs, Codes and Cryptography, 11(2):107\u2013122, 1997.","DOI":"10.1023\/A:1008216403325"},{"key":"9195_CR13","doi-asserted-by":"crossref","unstructured":"C. Blundo, A. De Santis, L. Gargano, and U. Vaccaro. On the information rate of secret sharing schemes. Theoretical Computer Science, 154(2):283\u2013306, 1996.","DOI":"10.1016\/0304-3975(95)00065-8"},{"key":"9195_CR14","doi-asserted-by":"crossref","unstructured":"C. Blundo, A. De Santis, D. R. Stinson, and U. Vaccaro. Graph decomposition and secret sharing schemes. J. of Cryptology, 8(1):39\u201364, 1995.","DOI":"10.1007\/BF00204801"},{"key":"9195_CR15","unstructured":"E. F. Brickell. Some ideal secret sharing schemes. Journal of Combin. Math. and Combin. Comput., 6:105\u2013113, 1989."},{"key":"9195_CR16","doi-asserted-by":"crossref","unstructured":"E. F. Brickell and D. M. Davenport. On the classification of ideal secret sharing schemes. J. of Cryptology, 4(73):123\u2013134, 1991.","DOI":"10.1007\/BF00196772"},{"key":"9195_CR17","doi-asserted-by":"crossref","unstructured":"S. Bublitz. Decomposition of graphs and monotone formula size of homogeneous functions. Acta Informatica, 23:689\u2013696, 1986.","DOI":"10.1007\/BF00264314"},{"key":"9195_CR18","doi-asserted-by":"crossref","unstructured":"R. M. Capocelli, A. De Santis, L. Gargano, and U. Vaccaro. On the size of shares for secret sharing schemes. J. of Cryptology, 6(3):157\u2013168, 1993.","DOI":"10.1007\/BF00198463"},{"key":"9195_CR19","doi-asserted-by":"crossref","unstructured":"D. Chaum, C. Cr\u00e9peau, and I. Damg\u00e5rd. Multiparty unconditionally secure protocols. In Proc. of the 20th ACM Symp. on the Theory of Computing, pages 11\u201319, 1988.","DOI":"10.1145\/62212.62214"},{"key":"9195_CR20","doi-asserted-by":"crossref","unstructured":"B. Chor and E. Kushilevitz. Secret sharing over infinite domains. J. of Cryptology, 6(2):87\u201396, 1993.","DOI":"10.1007\/BF02620136"},{"key":"9195_CR21","doi-asserted-by":"crossref","unstructured":"R. Cramer, I. Damg\u00e5rd, and U. Maurer. General secure multi-party computation from any linear secret-sharing scheme. In B. Preneel, editor, Advances in Cryptology \u2013 EUROCRYPT 2000, volume 1807 of Lecture Notes in Computer Science, pages 316\u2013334. Springer-Verlag, 2000.","DOI":"10.1007\/3-540-45539-6_22"},{"key":"9195_CR22","doi-asserted-by":"crossref","unstructured":"G. Di Crescenzo and C. Galdi. Hypergraph decomposition and secret sharing. Discrete Applied Mathematics, 157(5):928\u2013946, 2009.","DOI":"10.1016\/j.dam.2008.04.001"},{"key":"9195_CR23","doi-asserted-by":"crossref","unstructured":"L. Csirmaz. The size of a share must be large. J. of Cryptology, 10(4):223\u2013231, 1997.","DOI":"10.1007\/s001459900029"},{"key":"9195_CR24","unstructured":"L. Csirmaz. Secret sharing schemes on graphs. Technical Report 2005\/059, Cryptology ePrint Archive, 2005. eprint.iacr.org\/ ."},{"issue":"3","key":"9195_CR25","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/s10623-009-9304-0","volume":"53","author":"L Csirmaz","year":"2009","unstructured":"L. Csirmaz. An impossibility result on graph secret sharing. Designs, Codes and Cryptography, 53(3):195\u2013209, 2009.","journal-title":"Designs, Codes and Cryptography"},{"key":"9195_CR26","doi-asserted-by":"crossref","unstructured":"L. Csirmaz, P. Ligeti, and G. Tardos. Erd\u00f6s-pyber theorem for hypergraphs and secret sharing. Graphs and Combinatorics, 2014.","DOI":"10.1007\/s00373-014-1448-7"},{"key":"9195_CR27","unstructured":"L. Csirmaz and G. Tardos. Secret sharing on trees: problem solved. IACR Cryptology ePrint Archive, 2009:71, 2009."},{"key":"9195_CR28","doi-asserted-by":"crossref","unstructured":"Y. Desmedt and Y. Frankel. Shared generation of authenticators and signatures. In J. Feigenbaum, editor, Advances in Cryptology \u2013 CRYPTO \u201991, volume 576 of Lecture Notes in Computer Science, pages 457\u2013469. Springer-Verlag, 1992.","DOI":"10.1007\/3-540-46766-1_37"},{"key":"9195_CR29","doi-asserted-by":"crossref","unstructured":"M. van Dijk. On the information rate of perfect secret sharing schemes. Designs, Codes and Cryptography, 6:143\u2013169, 1995.","DOI":"10.1007\/BF01398012"},{"key":"9195_CR30","doi-asserted-by":"crossref","unstructured":"P. Erd\u00f6s and L. Pyber. Covering a graph by complete bipartite graphs. Discrete Mathematics, 170(1-3):249\u2013251, 1997.","DOI":"10.1016\/S0012-365X(96)00124-0"},{"key":"9195_CR31","doi-asserted-by":"crossref","unstructured":"O. Farr\u00e0s, J. Mart\u00ed-Farr\u00e9, and C. Padr\u00f3. Ideal multipartite secret sharing schemes. J. of Cryptology, 25(1):434\u2013463, 2012.","DOI":"10.1007\/s00145-011-9101-6"},{"key":"9195_CR32","doi-asserted-by":"crossref","unstructured":"A. G\u00e1l. A characterization of span program size and improved lower bounds for monotone span programs. In Proc. of the 30th ACM Symp. on the Theory of Computing, pages 429\u2013437, 1998.","DOI":"10.1145\/276698.276855"},{"key":"9195_CR33","doi-asserted-by":"crossref","unstructured":"A. G\u00e1l and P. Pudl\u00e1k. A note on monotone complexity and the rank of matrices. Inform. Process. Lett., 87:321\u2013326, 2003.","DOI":"10.1016\/S0020-0190(03)00334-X"},{"key":"9195_CR34","doi-asserted-by":"crossref","unstructured":"V. Goyal, O. Pandey, A. Sahai, and B. Waters. Attribute-based encryption for fine-grained access control of encrypted data. In Proc. of the 13th ACM Conference on Computer and Communications Security, pages 89\u201398, 2006.","DOI":"10.1145\/1180405.1180418"},{"key":"9195_CR35","unstructured":"M. Ito, A. Saito, and T. Nishizeki. Secret sharing schemes realizing general access structure. In Proc. of the IEEE Global Telecommunication Conf., Globecom 87, pages 99\u2013102, 1987. Journal version: Multiple assignment scheme for sharing secret. J. of Cryptology, 6(1):15\u201320, 1993."},{"key":"9195_CR36","doi-asserted-by":"crossref","unstructured":"M. Jerrum. A very simple algorithm for estimating the number of k-colorings of a low-degree graph. Random Structures & Algorithms, 7:157\u2013166, 1995.","DOI":"10.1002\/rsa.3240070205"},{"key":"9195_CR37","doi-asserted-by":"publisher","first-page":"55","DOI":"10.1002\/jgt.20367","volume":"61","author":"S Jukna","year":"2009","unstructured":"S. Jukna. On set intersection representations of graphs. Journal of Graph Theory, 61:55\u201375, 2009.","journal-title":"Journal of Graph Theory"},{"key":"9195_CR38","doi-asserted-by":"crossref","unstructured":"M. Karchmer and A. Wigderson. On span programs. In Proc. of the 8th IEEE Structure in Complexity Theory, pages 102\u2013111, 1993.","DOI":"10.1109\/SCT.1993.336536"},{"key":"9195_CR39","doi-asserted-by":"crossref","unstructured":"E. D. Karnin, J. W. Greene, and M. E. Hellman. On secret sharing systems. IEEE Trans. on Information Theory, 29(1):35\u201341, 1983.","DOI":"10.1109\/TIT.1983.1056621"},{"key":"9195_CR40","unstructured":"J. Kilian and N. Nisan. Private communication, 1990."},{"key":"9195_CR41","doi-asserted-by":"crossref","unstructured":"J. Mart\u00ed-Farr\u00e9 and C. Padr\u00f3. Secret sharing schemes on sparse homogeneous access structures with rank three. Electr. J. Comb., 11(1), 2004.","DOI":"10.37236\/1825"},{"key":"9195_CR42","doi-asserted-by":"crossref","unstructured":"J. Mart\u00ed-Farr\u00e9 and C. Padr\u00f3. Secret sharing schemes with three or four minimal qualified subsets. Designs, Codes and Cryptography, 34(1):17\u201334, 2005.","DOI":"10.1007\/s10623-003-4192-1"},{"key":"9195_CR43","doi-asserted-by":"crossref","unstructured":"J. Mart\u00ed-Farr\u00e9 and C. Padr\u00f3. On secret sharing schemes, matroids and polymatroids. Journal of Mathematical Cryptology, 4(2):95\u2013120, 2010.","DOI":"10.1515\/jmc.2010.004"},{"key":"9195_CR44","unstructured":"Y. Mintz. Information ratios of graph secret-sharing schemes. Master\u2019s thesis, Dept. of Computer Science, Ben Gurion University, 2012."},{"key":"9195_CR45","doi-asserted-by":"crossref","unstructured":"M. Mitzenmacher and E. Upfal. Probability and Computing. Cambridge University Press, 2005.","DOI":"10.1017\/CBO9780511813603"},{"key":"9195_CR46","doi-asserted-by":"crossref","unstructured":"M. Naor and A. Wool. Access control and signatures via quorum secret sharing. In 3rd ACM Conf. on Computer and Communications Security, pages 157\u2013167, 1996.","DOI":"10.1145\/238168.238209"},{"key":"9195_CR47","doi-asserted-by":"crossref","unstructured":"C. Padr\u00f3 and G. S\u00e1ez. Secret sharing schemes with bipartite access structure. IEEE Trans. on Information Theory, 46:2596\u20132605, 2000.","DOI":"10.1109\/18.887867"},{"key":"9195_CR48","doi-asserted-by":"crossref","unstructured":"C. Padr\u00f3 and G. S\u00e1ez. Lower bounds on the information rate of secret sharing schemes with homogeneous access structure. Inf. Process. Lett., 83(6):345\u2013351, 2002.","DOI":"10.1016\/S0020-0190(02)00213-2"},{"key":"9195_CR49","doi-asserted-by":"crossref","unstructured":"J. Salas and A. D. Sokal. Absence of phase transition for antiferromagnetic Potts models via the Dobrushin uniqueness theorem. J. Statist. Phys., 86:551\u2013579, 1997.","DOI":"10.1007\/BF02199113"},{"key":"9195_CR50","doi-asserted-by":"crossref","unstructured":"A. Shamir. How to share a secret. Communications of the ACM, 22:612\u2013613, 1979.","DOI":"10.1145\/359168.359176"},{"key":"9195_CR51","doi-asserted-by":"crossref","unstructured":"B. Shankar, K. Srinathan, and C. Pandu Rangan. Alternative protocols for generalized oblivious transfer. In Proceedings of the 9th International Conference on Distributed Computing and Networking (ICDCN\u201908), volume 4904 of Lecture Notes in Computer Science, pages 304\u2013309. Springer-Verlag, 2008.","DOI":"10.1007\/978-3-540-77444-0_31"},{"key":"9195_CR52","unstructured":"G. J. Simmons, W. Jackson, and K. M. Martin. The geometry of shared secret schemes. Bulletin of the ICA, 1:71\u201388, 1991."},{"key":"9195_CR53","doi-asserted-by":"crossref","unstructured":"D. R. Stinson. New general lower bounds on the information rate of secret sharing schemes. In E. F. Brickell, editor, Advances in Cryptology \u2013 CRYPTO \u201992, volume 740 of Lecture Notes in Computer Science, pages 168\u2013182. Springer-Verlag, 1993.","DOI":"10.1007\/3-540-48071-4_12"},{"key":"9195_CR54","doi-asserted-by":"crossref","unstructured":"D. R. Stinson. Decomposition construction for secret sharing schemes. IEEE Trans. on Information Theory, 40(1):118\u2013125, 1994.","DOI":"10.1109\/18.272461"},{"key":"9195_CR55","unstructured":"H. Sun and S. Shieh. Secret sharing in graph-based prohibited structures. In INFOCOM \u201997, pages 718\u2013724, 1997."},{"key":"9195_CR56","doi-asserted-by":"crossref","unstructured":"H.-M. Sun, H. Wang, B.-H. Ku, and J. Pieprzyk. Decomposition construction for secret sharing schemes with graph access structures in polynomial time. SIAM J. Discret. Math., 24:617\u2013638, 2010.","DOI":"10.1137\/080733802"},{"key":"9195_CR57","doi-asserted-by":"crossref","unstructured":"T. Tassa. Generalized oblivious transfer by secret sharing. Des. Codes Cryptography, 58(1):11\u201321, 2011.","DOI":"10.1007\/s10623-010-9378-8"},{"key":"9195_CR58","doi-asserted-by":"crossref","unstructured":"B. Waters. Ciphertext-policy attribute-based encryption: an expressive, efficient, and provably secure realization. In Proc. of the 14th International Conference on Practice and Theory in Public Key Cryptography, volume 6571 of Lecture Notes in Computer Science, pages 53\u201370. Springer-Verlag, 2011.","DOI":"10.1007\/978-3-642-19379-8_4"},{"key":"9195_CR59","doi-asserted-by":"crossref","unstructured":"I. Wegener. The Complexity of Boolean Functions. Wiley-Teubner, 1987.","DOI":"10.1007\/3-540-18170-9_185"}],"container-title":["Journal of Cryptology"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-014-9195-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00145-014-9195-8\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-014-9195-8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00145-014-9195-8.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,14]],"date-time":"2025-05-14T21:54:14Z","timestamp":1747259654000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00145-014-9195-8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2014,12,24]]},"references-count":59,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2016,4]]}},"alternative-id":["9195"],"URL":"https:\/\/doi.org\/10.1007\/s00145-014-9195-8","relation":{},"ISSN":["0933-2790","1432-1378"],"issn-type":[{"type":"print","value":"0933-2790"},{"type":"electronic","value":"1432-1378"}],"subject":[],"published":{"date-parts":[[2014,12,24]]},"assertion":[{"value":"26 June 2013","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"24 December 2014","order":2,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}