|
|
|
The optimal information rate for graph access structures of nine participants |
Yun SONG1,Zhihui LI1,*( ),Yongming LI2,Ren XIN3 |
1. College of Mathematics and Information Science, Shaanxi Normal University, Xi’an 710062, China
2. College of Computer Science, Shaanxi Normal University, Xi’an 710062, China
3. School of Civil Engineering, Xi’an University of Architecture and Technology, Xi’an 710055, China |
|
|
|
|
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
|
|
Corresponding Author(s):
Zhihui LI
|
|
Issue Date: 24 September 2015
|
|
| 1 |
Shamir A. How to share a secret. Communications of the ACM, 1979, 24: 612―613
https://doi.org/10.1145/359168.359176
|
| 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
https://doi.org/10.1016/j.ins.2013.08.012
|
| 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
https://doi.org/10.1016/j.jss.2014.01.001
|
| 5 |
Ulutas G, Ulutas M, Nabiyev V V. Secret image sharing scheme with adaptive authentication strength. Pattern Recognition Letters, 2013, 34(3): 283―291
https://doi.org/10.1016/j.patrec.2012.10.017
|
| 6 |
Lein H, Miao F Y. Multilevel threshold secret sharing based on the Chinese Remainder Theorem. Information Processing Letters, 2014, 114(9): 504―509
https://doi.org/10.1016/j.ipl.2014.04.006
|
| 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
https://doi.org/10.1007/BF02451112
|
| 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
https://doi.org/10.1016/j.ins.2013.03.047
|
| 9 |
Jackson W, Martin K M. Perfect secret sharing schemes on five participants. Designs, Codes and Cryptography, 1996, 9(3): 267―286
https://doi.org/10.1007/BF00129769
|
| 10 |
van Dijk M. On the information rate of perfect secret sharing schemes. Designs, Codes and Cryptography, 1995, 6(2): 143―169
https://doi.org/10.1007/BF01398012
|
| 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
https://doi.org/10.1007/978-3-642-25769-8_90
|
| 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
https://doi.org/10.1109/ICBMEI.2011.5917883
|
| 13 |
Sun H M, Chen B L. Weighted decomposition construction for perfect secret sharing schemes. Computers & Mathematics with Applications, 2002, 43(6): 877―887
https://doi.org/10.1016/S0898-1221(01)00328-5
|
| 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
https://doi.org/10.1007/s10623-011-9592-z
|
| 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
https://doi.org/10.1007/978-3-642-12200-2_31
|
| 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
https://doi.org/10.1007/BF00198463
|
| 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
|
| [1] |
Supplementary Material-Highlights in 3-page ppt
|
Download
|
|
Viewed |
|
|
|
Full text
|
|
|
|
|
Abstract
|
|
|
|
|
Cited |
|
|
|
|
| |
Shared |
|
|
|
|
| |
Discussed |
|
|
|
|
