Opening book details…
Can I read On Secret Sharing Schemes, Matroids and Polymatroids on EtoBox?
On Secret Sharing Schemes, Matroids and Polymatroids by Jaume Martí-Farré; Carles Padró is a Computer Science article available to read on EtoBox.
What is On Secret Sharing Schemes, Matroids and Polymatroids about?
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. We 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. These results precede the invention of secret sharing by Shamir in 1979. Important connections between ideal secret sharing schemes and matroids were discovered by Brickell and Davenport in 1991. Their results can be restated as follows: every ideal secret sharing scheme defines a matroid, and its access structure is a port of that matroid. Our main result is a lower bound on the optimal complexity of access structures that are not matroid ports. Namely, by using the aforementioned characterization of matroid ports by Seymour, we generalize the result by Brickell and Davenport by proving that, if the length of every share in a secret sharing scheme is less than 3=2 times the length of the secret,
Who reads On Secret Sharing Schemes, Matroids and Polymatroids?
It is typically read by researchers, students, and practitioners in Computer Science.
- Author
- Jaume Martí-Farré; Carles Padró
- Publisher
- Walter de Gruyter GmbH
- Published
- 2010
- Language
- DE
- Field
- Computer Science (Physical Sciences)