On Secret Sharing Schemes, Matroids and Polymatroids

Date Added: Jun 2009
Format: PDF

The complexity of a secret sharing scheme is defined as the ratio between the maximum length of the shares and the length of the secret. The optimization of this parameter for general access structures is an important and very difficult open problem in secret sharing. The authors explore in this paper the connections of this open problem with matroids and polymatroids. Matroid ports were introduced by Lehman in 1964. A forbidden minor characterization of matroid ports was given by Seymour in 1976.