You are looking at a specific version 20120818:034243 of this paper. See the latest version.

Paper 2012/464

Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming

Carles Padro and Leonor Vazquez and An Yang

Abstract

Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants. By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.

Note: This is a full version of the paper appeared in the Proceedings of LATIN 2010. Several new results have been added to the current version, as the ones in Sections 6 and 7. Moreover, the overall presentation of the paper has been greatly improved.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. A previous version of this paper appeared in the Proceedings of LATIN 2010.
Keywords
Secret sharinglinear programmingpolymatroidnon-Shannon information inequalities
Contact author(s)
yang0246 @ e ntu edu sg
History
2012-08-18: received
Short URL
https://ia.cr/2012/464
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.