Paper 2012/595

Extending Brickell-Davenport Theorem to Non-Perfect Secret Sharing Schemes

Oriol Farràs and Carles Padró

Abstract

One important result in secret sharing is the Brickell-Davenport Theorem: every ideal perfect secret sharing scheme defines a matroid that is uniquely determined by the access structure. Even though a few attempts have been made, there is no satisfactory definition of ideal secret sharing scheme for the general case, in which non-perfect schemes are considered as well. Without providing another unsatisfactory definition of ideal non-perfect secret sharing scheme, we present a generalization of the Brickell-Davenport Theorem to the general case. After analyzing that result under a new point of view and identifying its combinatorial nature, we present a characterization of the (not necessarily perfect) secret sharing schemes that are associated to matroids. Some optimality properties of such schemes are discussed.

Note: Revised version. A new section with examples added.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
Secret sharingNon-perfect secret sharing schemeMatroidPolymatroid
Contact author(s)
cpadro @ ma4 upc edu
History
2012-12-18: last of 2 revisions
2012-10-25: received
See all versions
Short URL
https://ia.cr/2012/595
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/595,
      author = {Oriol Farràs and Carles Padró},
      title = {Extending Brickell-Davenport Theorem to Non-Perfect Secret Sharing Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2012/595},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/595}},
      url = {https://eprint.iacr.org/2012/595}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.