The lower bound and exact value of the information rate of some developed graph access structures
Keywords:Graph access structure, Perfect secret sharing scheme, Information rate
Various studies have focused on secret sharing schemes and in all of them, each shareholder is interested in a shorter share. The information rate of a secret sharing scheme shows the ratio between the size of the secret to the maximum number of shares given to each shareholder. In this regard, the researchers investigated the optimal information rate of the graph access structure. This paper aims to discover the exact values for the optimal information rates of the two graph access structures, which remained as open problems in Van Dijk’s paper. Furthermore, we introduced the developed multipartite graph and the developed cycle graph and calculated the exact value of their optimal information rate. Moreover, we presented a lower bound on the information rate for other developed graph access structures.
C. Blundo, A. De Santis, D. R. Stinson, and U. Vaccaro, “Graph decompositions and secret sharing schemes”, Journal of cryptology, vol. 8, no. 1, pp. 39-64, Dec. 1995, doi: 10.1007/BF00204801
E. F. Brickell and D. R. Stinson, “Some improved bounds on the information rate of perfect secret sharing schemes”, Journal of cryptology, vol. 5, no. 3, pp. 153-166, Oct. 1992, doi: 10.1007/BF02451112
M. Gharahi and M. H. Dehkordi. “The complexity of the graph access structures on six participants”, Designs, codes and cryptography, vol. 67, no. 2, pp. 169-173, Dec. 2013, doi: 10.1007/s10623-011-9592-z
M. Gharahi and M. H. Dehkordi. “Perfect secret sharing schemes for graph access structures on six participants”, Journal of mathematical cryptology, vol. 7, no. 2, pp. 143-146, Sep. 2013, doi: 10.1515/jmc-2012-0026
K. Harsányi and P. Ligeti. “Exact information ratios for secret sharing on small graphs with girth at least 5”, Journal of mathematical cryptology, vol. 13, no. 2, pp. 107-116, Jun. 2019, doi: 10.1515/jmc-2018-0024
W.-A. Jackson and K. M. Martin. “Perfect secret sharing schemes on five participants”, Designs, codes and cryptography, vol. 9, no. 3, pp. 267-286, Nov. 1996, doi: 10.1007/BF00129769
H.-Ch. Lu and H.-L. Fu. “New bounds on the average information rate of secret-sharing schemes for graph-based weighted threshold access structures”, Information sciences, vol. 240, pp. 83-94, Aug. 2013, doi: 10.1016/j.ins.2013.03.047
P. Carles, L. Vázquez, and A. Yang. “Finding lower bounds on the complexity of secret sharing schemes by linear programming”, Discrete applied mathematics, vol. 161, no. 7-8, pp. 1072-1084, May 2013, doi: 10.1016/j.dam.2012.10.020
A. Shamir, “How to share a secret”, Communications of the ACM vol. 22, no. 11, pp. 612-613, Nov. 1979, doi:. 10.1145/359168.359176
Y. Song, L. Zhihui, L. Yongming, and X. Ren. “The optimal information rate for graph access structures of nine participants”, Frontiers of computer science, vol. 9, no. 5, pp. 778-787, Oct. 2015, doi:. 10.1007/s11704-015-3255-6
D. R. Stinson and M. B. Paterson, Cryptography: theory and practice, 4th ed. Boca Raton, FL: CRC Press Taylor & Francis Group, 2018.
M. Van Dijk, “On the information rate of perfect secret sharing schemes”, Designs, codes and cryptography, vol. 6, no. 2, pp. 143-169, Sep. 1995, doi: 10.1007/BF01398012
How to Cite
Copyright (c) 2020 Abbas Cheraghi
This work is licensed under a Creative Commons Attribution 4.0 International License.