Cryptology ePrint Archive: Report 2010/232

On Representable Matroids and Ideal Secret Sharing

Ching-Fang Hsu and Qi Cheng

Abstract: In secret sharing, the exact characterization of ideal access structures is a longstanding open problem. Brickell and Davenport (J. of Cryptology, 1991) proved that ideal access structures are induced by matroids. Subsequently, ideal access structures and access structures induced by matroids have attracted a lot of attention. Due to the difficulty of finding general results, the characterization of ideal access structures has been studied for several particular families of access structures. In all these families, all the matroids that are related to access structures in the family are representable and, then, the matroid-related access structures coincide with the ideal ones. In this paper, we study the characterization of representable matroids. By using the well known connection between ideal secret sharing and matroids and, in particular, the recent results on ideal multipartite access structures and the connection between multipartite matroids and discrete polymatroids, we obtain a characterization of a family of representable multipartite matroids, which implies a sufficient condition for an access structure to be ideal. By using this result and further introducing the reduced discrete polymatroids, we provide a complete characterization of quadripartite representable matroids, which was until now an open problem, and hence, all access structures related to quadripartite representable matroids are the ideal ones. By the way, using our results, we give a new and simple proof that all access structures related to unipartite, bipartite and tripartite matroids coincide with the ideal ones.

Category / Keywords: Cryptography, Ideal secret sharing schemes, Ideal access structures, Representable multipartite matroids, Discrete polymatroids.

Publication Info: unpublished

Date: received 24 Apr 2010, last revised 9 Oct 2010

Contact author: cherryjingfang at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20101009:063800 (All versions of this report)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]