پدافند الکترونیکی و سایبری

پدافند الکترونیکی و سایبری

کران‌های جدیدی بر روی نسبت اطلاعات ضرب دکارتی کلاس‌هایی از گراف‌ها

نوع مقاله : مقاله پژوهشی

نویسندگان
1 دانشکده ریاضی و کامپیوتر خوانسار
2 دانشگاه شهرکرد
چکیده
در این مقاله، یک کران پایینی برای نسبت اطلاعات حاصل­ضرب دکارتی یک درخت دلخواه با قطر حداقل 3 و دور  برای هر  خواهیم یافت. علاوه براین، بهترین نسبت اطلاعات طرح تسهیم راز کامل برپایه گراف  را تعیین می­کنیم که در آن،  گراف حاصل از ضرب دکارتی دور به طول 6 با گراف مکعب است. به‌طور دقیق­تر، نشان داده می­شود که برای هر ، نسبت اطلاعات  دقیقاً برابر با  است.
کلیدواژه‌ها

عنوان مقاله English

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

نویسندگان English

Abbas Cheraghi Chaleshtari 1
Mohammad Gholami 2
چکیده English

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
 
 

کلیدواژه‌ها English

Secret Sharing Scheme
Information Ratio
Cartesian Product
[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.##

  • تاریخ دریافت 23 دی 1396
  • تاریخ پذیرش 06 خرداد 1397
  • تاریخ انتشار 01 اسفند 1397