Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols / Secret sharing, Non-perfect secret sharing scheme, Matroid, Polymatroid

Date: received 19 Oct 2012, last revised 18 Dec 2012

Contact author: cpadro at ma4 upc edu

Available format(s): PDF | BibTeX Citation

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

Version: 20121218:102412 (All versions of this report)

Short URL: ia.cr/2012/595

Discussion forum: Show discussion | Start new discussion