The Optimal Information Rates of the Graph Access Structures on Seven Participants

Abstract:

The information rate is an important metric of the performance of a secret-sharing scheme. In this paper, we deal with determining the exact values for the optimal information rates of the six graph access structures and improving the information rate of a graph access structure on seven participants, which remained as open problems in Song's and Wang's paper([1,2]). We prove that the optimal information rate for each of the six graph access structures is equal to 4/7

• Periodical: Advanced Materials Research (Volume 859)
• Pages: 596-601
• DOI: https://doi.org/10.4028/www.scientific.net/AMR.859.596
• Online since: December 2013
• Authors: Zhi Hui Li, Yun Song, Yong Ming Li
• Keywords: Entropy Method, Graph Access Structure, Optimal Information Rate, Perfect Secret Sharing Scheme, Weighted Decomposition

References

[1] Y. Song, Z.H. Li, W. C. Wang, The information rate of secret sharing schemes based on seven participants by connect graphs,J. Recent advance in computer science and information engineering, CSIE 2011, Lecture notes in electrical engineering, vol. 127, 2012, pp.637-645.

DOI: 10.1007/978-3-642-25769-8_90

[2] W. C. Wang, Z.H. Li and Song Y, The optional information rate of perfect secret sharing schemes,J. In: Proceedings 2011 International Conference on Business Management and Electronic Information. vol. 2, May, 2011, pp.207-212.

DOI: 10.1109/icbmei.2011.5917883

[3] E.F. Brickell and D.R. Stinson, Some improved bounds on the information rate of perfect secret sharing schemes, J. Journal of Cryptology, vol. 5, pp.153-166, (1992).

DOI: 10.1007/bf02451112

[4] C. Blundo, A. De Santis, D.R. Stinson and U. Vaccaro, Graph decompositions and secret sharing schemes,J. Journal of Cryptology, vol. 8, pp.39-64, (1995).

DOI: 10.1007/bf00204801

[5] C. Padró and L. Vázquez, Finding lower bounds on the complexity of secret sharing schemes by linear programming, J. Discrete Applied Mathematics, vol. 161, pp.1072-1084, (2013).

DOI: 10.1016/j.dam.2012.10.020

[6] D .R. Stinson, An explication of secret sharing schemes, J. Designs, Codes and Cryptography, vol. 2, pp.357-390, (1992).

DOI: 10.1007/bf00125203

[7] W. Jackson and K.M. Martin, Perfect secret sharing schemes on five participants, J. Designs, Codes and Cryptography, vol. 9, pp.267-286, (1996).

DOI: 10.1007/bf00129769

[8] M. van Dijk, On the information rate of perfect secret sharing schemes, , J. Designs, Codes and Cryptography, vol. 6, pp.143-169, (1995).

DOI: 10.1007/bf01398012

[9] H. M. Sun and B. L. Chen, Weighted decomposition construction for perfect secret sharing schemes, , J. Computers & Mathematics with Applications, vol. 43, pp.877-887, (2002).

DOI: 10.1016/s0898-1221(01)00328-5

[10] M. Gharahi and M.H. Dehkordi, The complexity of the graph access structures on six participants. Designs, J. Codes and Cryptography, vol. 67, pp.169-173, (2013).

DOI: 10.1007/s10623-011-9592-z

[11] R. M. Capocelli, A . De Santis, L. Garg ano and U . Vaccaro. On the size of shares of secret sharing schemes, J, Journal of Cryptology, vol. 6, pp.157-168, (1993).

DOI: 10.1007/bf00198463

[12] T .M. Cover and J.A. Thomas. Elements of information theory. 2nd ed. New York: Wiley, (2006).

[13] D. R. Stinson. Cryptography theory and practice. 3rded. London, New York: Chapman & Hall/CRC, Boca Raton, (2006).

[14] L. Csirmaz, The size of a share must be large, J. Journal of Cryptology, vol. 10 , pp.223-231, (1997).

DOI: 10.1007/s001459900029