Top

Designs, Codes and Cryptography

Published in:

20-11-2022

Ideal hierarchical secret sharing and lattice path matroids

Author: Songbao Mo

Published in: Designs, Codes and Cryptography | Issue 4/2023

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

By a fundamental result by Brickell and Davenport (J Cryptol 4:123–134, 1991), the access structures of ideal secret sharing schemes are matroid ports. Farràs and Padró (IEEE Trans Inf Theory 58(5):3273–3286, 2012) presented a characterization of ideal hierarchical access structures. In this paper, we provide a different characterization. Specifically, we show that an access structure is ideal and hierarchical if and only if it is a port of a lattice path matroid at some specific points.

previous article Cayley sum graphs and their applications to codebooks

next article On the dimension and structure of the square of the dual of a Goppa code

Taking a cue from the concept of Isbel’s desirability relation [30] in game theory.

Ardila F.: The catalan matroid. J. Comb. Theory Ser. A 104(1), 49–62 (2003).MathSciNetCrossRefMATH

Beimel A.: Secret-sharing schemes: a survey. In: Chee Y.M., Guo Z., Ling S., Shao F., Tang Y., Wang H., Xing C. (eds.) Coding and Cryptology, vol. 6639, pp. 11–46. Lecture Notes in Computer Science. Springer, Berlin (2011).CrossRef

Blakley G.R.: Safeguarding cryptographic keys. AFIPS Conf. Proc. 48, 313–317 (1979).

Bonin J., de Mier A.: Lattice path matroids: structural properties. Eur. J. Comb. 27(5), 701–738 (2006).MathSciNetCrossRefMATH

Bonin J., Giménez O.: Multi-path matroids. Comb. Probab. Comput. 16(2), 193–217 (2007).MathSciNetCrossRefMATH

Bonin J., de Mier A., Noy M.: Lattice path matroids: enumerative aspects and Tutte polynomials. J. Comb. Theory Ser. A 104(1), 63–94 (2003).MathSciNetCrossRefMATH

Brickell E.: Some ideal secret sharing schemes. J. Comb. Math. Comb. Comput. 9, 105–113 (1989).MathSciNetMATH

Brickell E., Davenport D.: On the classification of ideal secret sharing schemes. J. Cryptol. 4, 123–134 (1991).CrossRefMATH

Crapo H.: Single-element extensions of matroids. J. Res. Natl. Bureau Stand. B 69B, 55–65 (1965).MathSciNetCrossRefMATH

10.

Farràs O., Padró C.: Ideal hierarchical secret sharing schemes. IEEE Trans. Inf. Theory 58(5), 3273–3286 (2012).MathSciNetCrossRefMATH

11.

Farràs O., Martí-Farré J., Padró C.: Ideal multipartite secret sharing schemes. J. Cryptol. 25, 434–463 (2012).MathSciNetCrossRefMATH

12.

Gvozdeva T., Hameed A., Slinko A.: Weightedness and structural characterization of hierarchical simple games. Math. Soc. Sci. 65(3), 181–189 (2013).MathSciNetCrossRefMATH

13.

Hameed A., Slinko A.: A characterisation of ideal weighted secret sharing schemes. J. Math. Cryptol. 9(4), 227–244 (2015).MathSciNetCrossRefMATH

14.

Ito M., Saito A., Nishizeki T.: Secret sharing scheme realizing any access structure. Proc. IEEE Glob. 87, 99–102 (1987).

15.

Karnin E.D., Greene J.W., Hellman M.E.: On secret sharing systems. IEEE Trans. Inf. Theory 29, 35–41 (1983).MathSciNetCrossRefMATH

16.

Klivans C.: Combinatorial properties of shifted complexes. Doctoral dissertation, Massachusetts Institute of Technology (2003).

17.

Lehman A.: A solution of the Shannon switching game. J. Soc. Ind. Appl. Math. 12, 687–725 (1964).MathSciNetCrossRefMATH

18.

Martí-Farré J., Padró C.: On secret sharing schemes, matroids and polymatroids. J. Math. Cryptol. 4, 95–120 (2010).MathSciNetCrossRefMATH

19.

Matúš F.: Matroid representations by partitions. Discret. Math. 203(1–3), 169–194 (1999).MathSciNetCrossRefMATH

20.

Oxley J.: Matroid Theory, 2. Oxford University Press, New York (2011).CrossRefMATH

21.

Oxley J., Prendergast K., Row D.: Matroids whose ground sets are domains of functions. J. Austral. Math. Soc. Ser. A 32, 380–387 (1982).MathSciNetCrossRefMATH

22.

Padró C., Sáez G.: Secret sharing schemes with bipartite access structure. IEEE Trans. Inf. Theory 46(7), 2596–2604 (2000).MathSciNetCrossRefMATH

23.

Padró C., Sáez G.: Correction to “Secret sharing schemes with bipartite access structure’’. IEEE Trans. Inf. Theory 50(6), 1373 (2004).CrossRefMATH

24.

Piff M.J., Welsh D.J.A.: On the vector representation of matroids. J. Lond. Math. Soc. 2, 284–288 (1970).MathSciNetCrossRef

25.

Seymour P.D.: On secret-sharing matroids. J. Comb. Theory Ser. B 56(1), 69–73 (1992).MathSciNetCrossRefMATH

26.

Shamir A.: How to share a secret. Commun. ACM 22, 612–613 (1979).MathSciNetCrossRefMATH

27.

Simonis J., Ashikhmin A.: Almost affine codes. Des. Codes Cryptogr. 14, 179–197 (1998).MathSciNetCrossRefMATH

28.

Stinson D.R.: An explication of secret sharing schemes. Des. Codes Cryptogr. 2(4), 357–390 (1992).MathSciNetCrossRefMATH

29.

Tassa T.: Hierarchical threshold secret sharing. J. Cryptol. 20, 237–264 (2007).MathSciNetCrossRefMATH

30.

Taylor A.D., Zwicker W.S.: Simple Games: Desirability Relations, Trading, Pseudoweightings. Princeton University Press, Princeton (1999).MATH

Title: Ideal hierarchical secret sharing and lattice path matroids
Author: Songbao Mo
Publication date: 20-11-2022
Publisher: Springer US
Published in: Designs, Codes and Cryptography / Issue 4/2023
Print ISSN: 0925-1022
Electronic ISSN: 1573-7586
DOI: https://doi.org/10.1007/s10623-022-01154-9

Springer Professional

Ideal hierarchical secret sharing and lattice path matroids

Abstract

Premium Partner

Springer Professional

Abstract

Please log in to get access to your license.

Other articles of this Issue 4/2023

Cyclic constant dimension subspace codes via the sum of Sidon spaces

A further study on the construction methods of bent functions and self-dual bent functions based on Rothaus’s bent function

Receiver selective opening security for identity-based encryption in the multi-challenge setting

The cycle structure of a class of permutation polynomials

Optimal quaternary -locally recoverable codes: their structures and complete classification

On inverses of permutation polynomials of the form over

Premium Partner