Paper 2003/151

Secret sharing schemes on sparse homogeneous access structures with rank three

Jaume Martí-Farré and Carles Padró

Abstract

One of the main open problems in secret sharing is the characterization of the ideal access structures. This problem has been studied for several families of access structures with similar results. Namely, in all these families, the ideal access structures coincide with the vector space ones and, besides, the optimal information rate of a non-ideal access structure is at most $2/3$. A first approach to the solution of that problem for the family of the $3$-homogeneous access structures is made in this paper. First, we present an ideal $3$-homogeneous access structure that is not vector space. Afterwards, we prove that the $3$-homogeneous access structures that can be realized by a ${\bf Z}_2$-vector space secret sharing scheme are {\em sparse\/}, that is, any subset of four participants contains at most two minimal qualified subsets. Finally, we solve the characterization problem for the family of the sparse $3$-homogeneous access structures. Specifically, we completely characterize the ideal access structures in this family, we prove that they coincide with the ${\bf Z}_2$-vector space ones and, besides, we demonstrate that there is no structure in this family having optimal information rate between $2/3$ and $1$. That is, we establish that the properties that were previously proved for several families also hold for the family of the sparse $3$-homogeneous access structures.

Note: 5 Jan 2007: Publication info updated

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. This is the preliminary version of the paper that appeared in ElectronicJournal of Combinatorics. A previous version appeared in the Proceedings of the International Workshop on Coding and Cryptography WCC 2003, Versailles, France.
Keywords
Secret sharingInformation rateIdeal secret sharing schemes.
Contact author(s)
matcpl @ mat upc es
History
2007-01-05: last of 2 revisions
2003-07-31: received
See all versions
Short URL
https://ia.cr/2003/151
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/151,
      author = {Jaume Martí-Farré and Carles Padró},
      title = {Secret sharing schemes on sparse homogeneous access structures with rank three},
      howpublished = {Cryptology ePrint Archive, Paper 2003/151},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/151}},
      url = {https://eprint.iacr.org/2003/151}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.