A remark on hierarchical threshold secret sharing

• Autorzy: Kawa R. , Kula M.

Identyfikatory

DOI

10.2478/v10065-012-0020-4

• Języki publikacji: EN

Abstrakty

EN

The main results of this paper are theorems which provide a solution to the open problem posed by Tassa [1]. He considers a specific family Γv of hierarchical threshold access structures and shows that two extreme members Γ∧ and Γv of Γv are realized by secret sharing schemes which are ideal and perfect. The question posed by Tassa is whether the other members of Γv can be realized by ideal and perfect schemes as well. We show that the answer in general is negative. A precise definition of secret sharing scheme introduced by Brickell and Davenport in [2] combined with a connection between schemes and matroids are crucial tools used in this paper. Brickell and Davenport describe secret sharing scheme as a matrix M with n+1 columns, where n denotes the number of participants, and define ideality and perfectness as properties of the matrix M. The auxiliary theorems presented in this paper are interesting not only because of providing the solution of the problem. For example, they provide an upper bound on the number of rows of M if the scheme is perfect and ideal.

Słowa kluczowe

EN

secret sharing scheme; hierarchical threshold access structure; matroid

• Wydawca: Wydawnictwo UMCS
• Czasopismo: Annales Universitatis Mariae Curie-Skłodowska. Sectio AI, Informatica
• Rocznik: 2012
• Tom: Vol. 12, no. 3
• Strony: 55--64
• Opis fizyczny: Bibliogr. 10 poz.

Twórcy

autor

Kawa R.

• Institute of Mathematics, University of Silesia, Bankowa 14, 40-007 Katowice, Poland

autor

Kula M.

• Institute of Mathematics, University of Silesia, Bankowa 14, 40-007 Katowice, Poland

Bibliografia

• [1] Tassa T., Hierarchical Threshold Secret Sharing, Journal of Cryptology 20 (2007): 237.
• [2] Brickell E., Davenport D., On the Classification of Ideal Secret Sharing Schemes, Journal of Cryptology 4 (1991): 123.
• [3] Blakley G. R., Safeguarding Cryptographic Keys, Proceedings of the National Computer Conference 48 (1979): 313.
• [4] Shamir A., How to Share a Secret, Communications of the ACM 22 (1979): 612.
• [5] Ito M., Saito A., Nishizeki T., Secret Sharing Scheme Realizing General Access Structure, Proceedings of the IEEE Global Telecommunications Conference (1987): 99.
• [6] Benaloh J., Leichter J., Generalized Secret Sharing and Monotone Functions, Proceedings of the Annual International Cryptology Conference on Advances in Cryptology (1988): 27.
• [7] Simmons G.J., How to (really) Share a Secret, Advances in Cryptology - CRYPTO 88 (1990): 390.
• [8] Farràs O. Padró C., Ideal Hierarchical Secret Sharing Schemes, Theory of Cryptography 5978 (2010): 219.
• [9] Oxley J. G., Matroid Theory, Oxford University Press, New York (1992).
• [10] Martí-Farré J., Padró C., Secret Sharing Schemes on Sparse Homogeneous Access Structures with Rank Three, The electronic journal of combinatorics 11 (2004): 1.