{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T15:37:22Z","timestamp":1787326642865,"version":"build-2736575974"},"reference-count":32,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"2","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Discrete Math."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>The purpose of this paper is to describe a new decomposition construction for perfect secret sharing schemes with graph access structures. The previous decomposition construction proposed by Stinson is a recursive method that uses small secret sharing schemes as building blocks in the construction of larger schemes. When the Stinson method is applied to the graph access structures, the number of such \u201csmall\u201d schemes is typically exponential in the number of the participants, resulting in an exponential algorithm. Our method has the same flavor as the Stinson decomposition construction; however, the linear programming problem involved in the construction is formulated in such a way that the number of \u201csmall\u201d schemes is polynomial in the size of the participants, which in turn gives rise to a polynomial time construction. We also show that if we apply the Stinson construction to the \u201csmall\u201d schemes arising from our new construction, both have the same information rate.<\/jats:p>","DOI":"10.1137\/080733802","type":"journal-article","created":{"date-parts":[[2010,6,20]],"date-time":"2010-06-20T21:18:25Z","timestamp":1277068705000},"page":"617-638","source":"Crossref","is-referenced-by-count":6,"title":["Decomposition Construction for Secret Sharing Schemes with Graph Access Structures in Polynomial Time"],"prefix":"10.1137","volume":"24","author":[{"given":"Hung-Min","family":"Sun","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Huaxiong","family":"Wang","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Bying-He","family":"Ku","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Josef","family":"Pieprzyk","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2010,6,18]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480104445654"},{"key":"R2","doi-asserted-by":"crossref","unstructured":"J. C. Benaloh and J. Leichter,\n                      Generalized secret sharing and monotone functions\n                      , in Proceedings of Advances in Cryptology\u2014CRYPTO'88, Lecture Notes in Comput. Sci. 403, Springer-Verlag, London, 1988, pp. 27\u201335.","DOI":"10.1007\/0-387-34799-2_3"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"B. Blakley, G. R. Blakley, A. H. Chan, and J. L. Massey,\n                      Threshold schemes with disenrollment\n                      , in Advances in Cryptology\u2014CRYPTO'92, Proceedings of the 12th Annual International Cryptology Conference, Santa Barbara, CA, 1992, Lecture Notes in Comput. Sci. 740, Springer-Verlag, London, 1992, pp. 540\u2013548.","DOI":"10.1007\/3-540-48071-4_38"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"G. R. Blakley,\n                      Safeguarding cryptographic keys\n                      , in Proceedings of the American Federation of Information Processing Societies Records (AFIPS1979) National Computer Conference, Vol. 48, 1979, pp. 313\u2013317.","DOI":"10.1109\/MARK.1979.8817296"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008216403325"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/BF00204801"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1007\/BF00196772"},{"key":"R8","doi-asserted-by":"publisher","DOI":"10.1007\/BF02451112"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1016\/j.dam.2008.04.001"},{"key":"R10","doi-asserted-by":"publisher","DOI":"10.1007\/s00607-009-0039-6"},{"key":"R11","unstructured":"M. Ito, A. Saito, and T. Nishizeki,\n                      Secret sharing scheme realizing general access structure\n                      , in Proceedings of IEEE Global Communications (Globecom'87), Tokyo, 1987, pp. 99\u2013102."},{"key":"R12","doi-asserted-by":"publisher","DOI":"10.1007\/BF02620229"},{"key":"R13","doi-asserted-by":"publisher","DOI":"10.1007\/BF00129769"},{"key":"R14","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579150"},{"key":"R15","first-page":"191","volume":"20","author":"Khachian L. G.","year":"1979","journal-title":"Soviet Math. Dokl.","ISSN":"https:\/\/id.crossref.org\/issn\/0197-6788","issn-type":"print"},{"key":"R16","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2006.871050"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.907505"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1007\/s10623-003-4192-1"},{"key":"R19","doi-asserted-by":"publisher","DOI":"10.1145\/358746.358762"},{"key":"R20","doi-asserted-by":"publisher","DOI":"10.1109\/18.887867"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1016\/S0020-0190(02)00213-2"},{"key":"R22","doi-asserted-by":"publisher","DOI":"10.1145\/359168.359176"},{"key":"R23","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2007.899541"},{"key":"R24","doi-asserted-by":"publisher","DOI":"10.1007\/BF00125203"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1109\/18.272461"},{"key":"R26","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(01)00328-5"},{"key":"R27","doi-asserted-by":"publisher","DOI":"10.1016\/S0898-1221(99)00049-8"},{"key":"R28","doi-asserted-by":"crossref","unstructured":"P. M. Vaidya,\n                      An algorithm for linear programming which requires $o(((m+n)n^ 2 + (m + n)^{ 1.5} n)l)$ arithmetic operations\n                      , in Proceedings of the Nineteenth Annual ACM Conference on Theory of Computing, 1987, pp. 29\u201338.","DOI":"10.1145\/28395.28399"},{"key":"R29","doi-asserted-by":"publisher","DOI":"10.1007\/BF01398012"},{"key":"R30","doi-asserted-by":"publisher","DOI":"10.1023\/A:1008381427667"},{"key":"R31","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.01.016"},{"key":"R32","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2005.860412"}],"container-title":["SIAM Journal on Discrete Mathematics"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/080733802","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T14:34:10Z","timestamp":1787322850000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/080733802"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":32,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1137\/080733802"],"URL":"https:\/\/doi.org\/10.1137\/080733802","relation":{},"ISSN":["0895-4801","1095-7146"],"issn-type":[{"value":"0895-4801","type":"print"},{"value":"1095-7146","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]}}}