J. Martí-Farré, C.
Padró
On Secret Sharing Schemes, Matroids
and Polymatroids
Extended version of the paper that appeared in
Fourth IACR Theory of
Cryptography Conference TCC 2007, Lecture Notes in Computer Science 4392 (2007) 273-290.
Abstract
One of the main open problems in secret sharing is the
characterization of the access structures of ideal secret sharing
schemes. As a consequence of the results by Brickell and Davenport,
every one of those access structures is related in a certain way to a
unique matroid.
Matroid ports are combinatorial objects that are almost equivalent to
matroid-related access structures. They were introduced by Lehman in
1964 and a forbidden minor characterization was given by Seymour in
1976. These and other subsequent works on that topic have not been
noticed until now by the researchers interested on secret sharing.
By combining those results with some techniques in secret sharing, we
obtain new characterizations of matroid-related access structures. As a
consequence, we generalize the result by Brickell and Davenport by
proving that, if the information rate of a secret sharing scheme is
greater than $2/3$, then its access structure is matroid-related. This
generalizes several results that were obtained for particular families
of access structures.
In addition, we study the use of polymatroids for obtaining upper
bounds on the optimal information rate of access structures. We prove
that every bound that is obtained by this technique for an access
structure applies to its dual structure as well.
Finally, we present lower bounds on the optimal information rate of the
access structures that are related to two matroids that are not
associated with any ideal secret sharing scheme: the Vamos matroid and
the non-Desargues matroid.
Download full version: sssmp.pdf (updated on
23 Oct 2007)