International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

On Representable Matroids and Ideal Secret Sharing

Authors:
Chingfang Hsu
Qi Cheng
Download:
URL: http://eprint.iacr.org/2010/232
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2010-23133,
  title={On Representable Matroids and Ideal Secret Sharing},
  booktitle={IACR Eprint archive},
  keywords={Cryptography, Ideal secret sharing schemes, Ideal access structures, Representable multipartite matroids, Discrete polymatroids.},
  url={http://eprint.iacr.org/2010/232},
  note={unpublished cherryjingfang@gmail.com 14785 received 24 Apr 2010, last revised 25 Jun 2010},
  author={Chingfang Hsu and Qi Cheng},
  year=2010
}