Decomposition construction fo r secret sharing schemes with graph access structures in polynomial time

Hung Min Sun*, Huaxiong Wang, Bying He Ku, Josef Pieprzyk

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)
5 Downloads (Pure)


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 "small" 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 "small" 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 "small" schemes arising from our new construct ion, both have the same information rate.

Original languageEnglish
Pages (from-to)617-638
Number of pages22
JournalSIAM Journal on Discrete Mathematics
Issue number2
Publication statusPublished - 2010

Bibliographical note

Copyright SIAM Publications. Article archived for private and non-commercial use with the permission of the author and according to publisher conditions. For further information see


Dive into the research topics of 'Decomposition construction fo r secret sharing schemes with graph access structures in polynomial time'. Together they form a unique fingerprint.

Cite this