The optimal information rate for graph access structures of nine participants

Abstract

The information rate is an important metric of the performance of a secret-sharing scheme. In this paper we consider 272 non-isomorphic connected graph access structures with nine vertices and eight or nine edges, and either determine or bound the optimal information rate in each case. We obtain exact values for the optimal information rate for 231 cases and present a method that is able to derive information-theoretical upper bounds on the optimal information rate. Moreover, we apply some of the constructions to determine lower bounds on the information rate. Regarding information rate, we conclude with a full listing of the known optimal information rate (or bounds on the optimal information rate) for all 272 graphs access structures of nine participants.

Keywords

optimal information rate / perfect secret-sharing scheme / entropy method / graph access structure / splitting construction / L-decomposition / weighted decomposition

References

[1] Shamir A. How to share a secret. Communications of the ACM, 1979, 24: 612―613

[2] Blakley G R. Safeguarding cryptographic keys. Proceedings of AFIPS National Computer Conference. 1979, 48: 313―317

[3] Yuan H D. Secret sharing with multi-cover adaptive steganography. Information Sciences, 2014, 254(1): 197―212

[4] Chen C C, Wu W J. A secure Boolean-based multi-secret image sharing scheme. Journal of Systems and Software, 2014, 92(7): 107―114

[5] Ulutas G, Ulutas M, Nabiyev V V. Secret image sharing scheme with adaptive authentication strength. Pattern Recognition Letters, 2013, 34(3): 283―291

[6] Lein H, Miao F Y. Multilevel threshold secret sharing based on the Chinese Remainder Theorem. Information Processing Letters, 2014, 114(9): 504―509

[7] Brickell E F, Stinson D R. Some improved bounds on the information rate of perfect secret sharing schemes. Journal of Cryptology, 1992, 5(3): 153―166

[8] Lu H C, Fu H L. New bounds on the average information rate of secretsharing schemes for graph-based weighted threshold access tructures. Information Sciences, 2013, 240(10): 83―94

[9] Jackson W, Martin K M. Perfect secret sharing schemes on five participants. Designs, Codes and Cryptography, 1996, 9(3): 267―286

[10] van Dijk M. On the information rate of perfect secret sharing schemes. Designs, Codes and Cryptography, 1995, 6(2): 143―169

[11] Song Y, Li ZH, Wang WC. The information rate of secret sharing schemes based on seven participants by connect graphs. Lecture Notes in Electrical Engineering, 2012, 127: 637―645

[12] Wang W C, Li Z H, Song Y. The optional information rate of perfect secret sharing schemes. In: Proceedings of the 2011 International Conference on Business Management and Electronic Information. 2011, 207―212

[13] Sun H M, Chen B L. Weighted decomposition construction for perfect secret sharing schemes. Computers & Mathematics with Applications, 2002, 43(6): 877―887

[14] Gharahi M, Dehkordi M H. The complexity of the graph access structures on six participants. Designs, Codes and Cryptography, 2013, 67(2): 169―173

[15] Padríő C, Víćzquez L. Finding lower bounds on the complexity of secret sharing schemes by linear prog ramming. Lecture Notes in Computer Science, 2010, 6034: 344―355

[16] Capocelli R M, De Santis A, Gargano L, Vaccaro U. On the size of shares of secret sharing schemes. Journal of Cryptology, 1993, 6(3): 157―168

[17] Cover T M, Thomas J A. Elements of Information Theory. 2nd ed. Wiley: New York, 2006

[18] Stinson D R. Cryptography theory and practice. 3rd ed. CRC/C&H, 2009

RIGHTS & PERMISSIONS

Higher Education Press and Springer-Verlag Berlin Heidelberg