Some New Bounds on the Information Ratio of the Cartesian Product of Some Classes of Graphs

Document Type : Original Article

Authors

Abstract

In this paper, we find a lower-bound for the information ratio of the cartesian product of an arbitrary tree         with diameter at least  3 and a cycle Cm  for every m³3. Moreover, we determine the best information ratio of           the perfect secret sharing scheme based on the graph  constructed from the cartesian product of a cycle of  length 6 with  the d -dimensional cube Qd . More precisely, it is shown that for every d³1 , the information ratio of  is exactly
 
 

Keywords

References

[1]      A. Shamir, “How to share a secret,” Comm. ACM, vol. 22, pp. 612-613, 1979.##
[2]      G. R. Blakley, “Safe guarding cryptographic keys,” in AFIPS Conference Proceedings, New York, United States of America, pp. 313-317, June 4-7, 1979.##
[3]       C. Blundo, et al., “On the information rate of secret sharing schemes,” Theor. Comput. Sci., vol. 154, no. 2, pp. 283-306, 1996.##
[4]       L. Csirmaz, “The size of a share must be large,” J. Cryptol, vol. 10, pp. 223-231, 1997.##
[5]      C. Blundo, A. De Santis, D. R. Stinson, and U. Vaccaro, “Graph decomposition and secret sharing schemes,” J. Cryptol, vol. 8, pp. 39-64, 1995.##
[6]      E. F. Brickell and D. M. Davenport, “On the classification of ideal secret sharing schemes,” J. Cryptol, vol. 4, pp. 123-134, 1991.##
[7]      E. F. Brickell and D. R. Stinson, “Some improved bounds on the information rate of perfect secret sharing schemes,” J. Cryptol, vol. 5, pp. 153-166, 1992.##
[8]      J. Martí-Farré and P. Carles “On secret sharing schemes, matroids and polymatroids,” J. Math. Cryptol, vol. 4, pp. 95-120, 2010.##
[9]      M. Van Dijk, “On the information rate of perfect secret sharing schemes,” Design. Code. Cryptogr., vol. 6, pp. 143-160, 1995.##
[10]    W. A. Jackson and K. M. Martin, “Perfect secret sharing schemes on five participants,” Design. Code. Cryptogr, vol. 9, pp. 267-286, 1996.##
[11]   C. Padro, “Lecture notes in secret sharing,” Available at http://eprint.iacr.org/2012/674, 2012.##
[12]   M. Gharahi and S. Khazaei, “Reduced access structures with four minimal qualified subsets on six participants,” Adv. Math. Commun. vol. 12, pp. 199-214, 2018.##
[13]   L. Csirmaz and G. Tardos, “Optimal information rate of secret sharing schemes on trees,” IEEE Trans. Inf. Theory, vol. 59, pp. 2527-2530, 2013.##
[14]   L. Csirmaz and P. Ligeti, “On an infinite family of graphs with information ratio 2−1/k,” Computing, vol. 85, pp. 127-136, 2009.##
[15]   L. Csirmaz, “Secret sharing on the d-dimensional cube,” Design. Code. Cryptogr, vol. 74, pp.  719-729, 2015.##
[16]    A. Cheraghi, G. Raeisi and M. Gholami, “On the information ratio of a class of graphs,” First International Conference on Combinatorics, Cryptography and Computation, I4C2016, IUST, Nour branch, Mazandaran, Iran, Sep. 2016.##
[17]   D. R. Stinson, “Decomposition construction for secret sharing schemes,” IEEE Trans. Inf. Theory, vol 40, pp. 118-125, 1994.##
[18]   W. Wang, Z. Li, and Y. Song, “The optimal information rate of perfect secret sharing schemes,” In 2011 International Conference on Business Management and Electronic Information (BMEI), Guangzhou, China, May 13-15, pp. 207-212, 2011.##
[19]   Z. Karimifard, S. Mashhadi, and D. Ebrahimi Bagha, “Semiquantum Secret Sharing Using Three Particles Without
Entanglement,” Journal of Electronical & Cyber Defence, vol. 4, no. 3, 2016.##
[20]   H. Maimani, Z. Norozi, “Secret sharing based on Cartesian product of graphs”, Iranian J. Math. Sci. Info, vol. 8, pp. 31-38, 2013.##
[21]   L. Csirmaz, “Secret sharing on infinite graphs,” Tetra Mount. Math. Pub, vol. 41, pp.1-18, 2008.##

Files

History

  • Receive Date: 13 January 2018
  • Accept Date: 27 May 2018
  • Publish Date: 20 February 2019

Share

How to cite

Statistics