On secret-sharing matroids

P. D. Seymour

doi:10.1016/0095-8956(92)90007-K

On secret-sharing matroids

P. D. Seymour

Research output: Contribution to journal › Article › peer-review

66 Scopus citations

Abstract

A matroid M is secret-sharing if there is a finite set S and a matrix A = (a_ij: i ∈ I, j ∈ E(M)) with entries in S, such that for all X ⊇ E(M), the submatrix (a_ij : i ∈ I, j ∈ X) has precisely |S|^rk(χ) distinct rows. Such matroids occur naturally in the study of secret-sharing schemes in cryptography. Brickell and Davenport (J. Cryptography, to appear) asked if every matroid is a secret-sharing matroid. We answer this negatively, by showing that the Vamos matroid is not.

Original language	English (US)
Pages (from-to)	69-73
Number of pages	5
Journal	Journal of Combinatorial Theory, Series B
Volume	56
Issue number	1
DOIs	https://doi.org/10.1016/0095-8956(92)90007-K
State	Published - Sep 1992
Externally published	Yes

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/0095-8956(92)90007-K

Cite this

@article{764226cdda794a74944681ae879e9e2d,

title = "On secret-sharing matroids",

abstract = "A matroid M is secret-sharing if there is a finite set S and a matrix A = (aij: i ∈ I, j ∈ E(M)) with entries in S, such that for all X ⊇ E(M), the submatrix (aij : i ∈ I, j ∈ X) has precisely |S|rk(χ) distinct rows. Such matroids occur naturally in the study of secret-sharing schemes in cryptography. Brickell and Davenport (J. Cryptography, to appear) asked if every matroid is a secret-sharing matroid. We answer this negatively, by showing that the Vamos matroid is not.",

author = "Seymour, {P. D.}",

year = "1992",

month = sep,

doi = "10.1016/0095-8956(92)90007-K",

language = "English (US)",

volume = "56",

pages = "69--73",

journal = "Journal of Combinatorial Theory, Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "1",

}

TY - JOUR

T1 - On secret-sharing matroids

AU - Seymour, P. D.

PY - 1992/9

Y1 - 1992/9

N2 - A matroid M is secret-sharing if there is a finite set S and a matrix A = (aij: i ∈ I, j ∈ E(M)) with entries in S, such that for all X ⊇ E(M), the submatrix (aij : i ∈ I, j ∈ X) has precisely |S|rk(χ) distinct rows. Such matroids occur naturally in the study of secret-sharing schemes in cryptography. Brickell and Davenport (J. Cryptography, to appear) asked if every matroid is a secret-sharing matroid. We answer this negatively, by showing that the Vamos matroid is not.

AB - A matroid M is secret-sharing if there is a finite set S and a matrix A = (aij: i ∈ I, j ∈ E(M)) with entries in S, such that for all X ⊇ E(M), the submatrix (aij : i ∈ I, j ∈ X) has precisely |S|rk(χ) distinct rows. Such matroids occur naturally in the study of secret-sharing schemes in cryptography. Brickell and Davenport (J. Cryptography, to appear) asked if every matroid is a secret-sharing matroid. We answer this negatively, by showing that the Vamos matroid is not.

UR - http://www.scopus.com/inward/record.url?scp=38249009286&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=38249009286&partnerID=8YFLogxK

U2 - 10.1016/0095-8956(92)90007-K

DO - 10.1016/0095-8956(92)90007-K

M3 - Article

AN - SCOPUS:38249009286

SN - 0095-8956

VL - 56

SP - 69

EP - 73

JO - Journal of Combinatorial Theory, Series B

JF - Journal of Combinatorial Theory, Series B

IS - 1

ER -

On secret-sharing matroids

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this