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.
Category / Keywords: cryptographic protocols / Secret sharing, linear programming, polymatroid, non-Shannon information inequalities Publication Info: A previous version of this paper appeared in the Proceedings of LATIN 2010. Date: received 14 Aug 2012, last revised 14 Aug 2012 Contact author: yang0246 at e ntu edu sg Available format(s): PDF | BibTeX Citation 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. Version: 20120818:034243 (All versions of this report) Short URL: ia.cr/2012/464 Discussion forum: Show discussion | Start new discussion