Ideal secret sharing schemes on graph-based $3$-homogeneous access structures

Document Type : Research Paper

Authors

1 Electrical and computer faculty, Malek Ashtar University of Technology, Tehran, Iran

2 Department of Mathematics and Cryptography, Malek Ashtar University of Technology, Isfahan, Iran

Abstract

‎The characterization of the ideal access structures is one of the main open problems in secret sharing and is important from both practical and theoretical points of views‎. ‎A graph-based $3-$homogeneous access structure is an access structure in which the participants are the vertices of a connected graph and every subset of the vertices is a minimal qualified subset if it has three vertices and induces a connected graph‎. ‎In this paper‎, ‎we introduce the graph-based $3-$homogeneous access structures and characterize the ideal graph-based $3$-homogeneous access structures‎. ‎We prove that for every non-ideal graph-based $3$-homogeneous access structure over the graph $G$ with the maximum degree $d$ there exists a secret sharing scheme with an information rate $\frac{1}{d+1}$‎. ‎Furthermore‎, ‎we mention three forbidden configurations that are useful in characterizing other families of ideal access structures‎.

Keywords

Main Subjects

References

[1] B. Bagherpour, S. Janbaz and A. Zaghian, Optimal information ratio of secret sharing schemes on Dutch Windmill
graphs, Adv. Math. Commun., 13 (2019) 88–99.
[2] G. R. Blakley, Safeguarding cryptographic keys, In proceeding of the AFIPS conference, 48 (1979) 313–317.
[3] C. Blundo, A. De Santis, R. De Simone and U. Vaccaro, Tight bounds on the information rate of the secret sharing
scheme, Des. Codes Cryptogr., 11 (1997) 107-122.
[4] C. Blundo, A. De Santis, D. R. Stinson and U. Vaccaro, Graph decomposition and secret sharing schemes, J.
Cryptology, 8 (1998) 39–64.
[5] E. F. Brickell and D. M. Davenport, On the classification of ideal secret sharing schemes, Journal of Cryptology,
4 (1991) 123–134.
[6] L. Csirmas and G. Tardos, Optimal information rate of the secret sharing schemes on trees, IEEE Transaction on
information theory, 59 (2013).
[7] W. Jackson and K. M. Martin, Perfect secret sharing schemes on five participants, Des. Codes Cryptogr., 9 (1996)
267–286.
[8] J. Martı́-Farré and C. Padró, Secret sharing schemes with three or four minimal qualified subsets, Des. Codes
Cryptogr., 34 (2005) 17–34.
[9] J. Martı́-Farré, A note on secret sharing schemes with three homogeneous access structure, Inform. Process. Lett.,
102 (2007) 133–137.
[10] J. Martı́-Farré and C. Padró, Ideal secret sharing scheme whose minimal qualified subsets have at most three
participants, Des. Codes Cryptogr., 52 (2009) 1–14.
[11] J. Martı́-Farré and C. Padró, Secret sharing schemes on access structures with intersection number equal to one,
Discrete Appl. Math., 154 (2006) 552–563.
[12] J. Martı́-Farré and C. Padró, Secret sharing schemes on sparse homogeneous access structures with rank three,
Electron. J. Combin., 11 (2004) 16 pp.
[13] M. Ito, A. Saito and T. Nishizeki, Secret sharing scheme realizing any access structure, Proc. IEEE Globecom, 87
(1987) 99–102.
[14] C. Padró and G. Sáez, Secret sharing with bipartite access structure, IEEE Trans. Inform. Theory, 46 (2000)
2596–2604.
[15] C. Padró and G. Sáez, Lower bounds on the information rate of secret sharing schemes with homogeneous access
structure, Inform. Process. Lett., 83 (2002) 345-351.
[16] A. Shamir, How to share a secret, Comm. ACM, 22 (1979) 612–613.
[17] D. R. Stinson, An explanation of secret sharing scheme, Designs, Codes and Cryptography, (1992) 157–390.
[18] D. R. Stinson, Decomposition construction for secret sharing schemes, IEEE Trans. Inform. Theory, 40 (1994)
118-125.
[19] T. Tassa and N. Dyn, Multipartite secret sharing by bivariate interpolation, J. Cryptology, 22 (2009) 227-258.
[20] T. Tassa, Hierarchical Threshold Secret Sharing, J. Cryptology, 20 (2007) 237-264.

Files

History

  • Receive Date: 23 June 2020
  • Revise Date: 18 January 2021
  • Accept Date: 26 January 2021
  • Published Online: 01 June 2021

Share

How to cite

Statistics