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

Category / Keywords: cryptographic protocols / Secret sharing, Information rate, Ideal secret sharing schemes.

Publication Info: 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.

Date: received 30 Jul 2003, last revised 5 Jan 2007

Contact author: matcpl at mat upc es

Available format(s): PDF | BibTeX Citation

Note: 5 Jan 2007: Publication info updated

Version: 20070105:120513 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]