On the Information Ratio of Graphs with Many Leaves

Gyarmati, Máté; Ligeti, Péter

doi:10.2478/tmmp-2019-0008

Abstract

We investigate the information ratio of graph-based secret sharing schemes. This ratio characterizes the efficiency of a scheme measured by the amount of information the participants must remember for each bits in the secret.

We examine the information ratio of several systems based on graphs with many leaves, by proving non-trivial lower and upper bounds for the ratio. On one hand, we apply the so-called entropy method for proving that the lower bound for the information ratio of n-sunlet graphs composed of a 1-factor between the vertices of a cycle C_n and n independent vertices is 2. On the other hand, some symmetric and recursive constructions are given that yield the upper bounds. In particular, we show that the information ratio of every graph composed of a 1-factor between a complete graph K_n and at most 4 independent vertices is smaller than 2.

References

[1] BLAKLEY, G. R.: Safeguarding cryptographic keys. In: Proc. of the Nat. Comp. Conf. Vol. 48, 1979, pp. 313–317.10.1109/MARK.1979.8817296
Search in Google Scholar Back to article
[2] BLUNDO, C.—DE SANTIS, A.—DE SIMONE, R.—VACCARO, U.: Tight bounds on the information rate of secret sharing schemes, Des. Codes Cryptogr. 11 (1997), 107–122.10.1023/A:1008216403325
Search in Google Scholar Back to article
[3] BLUNDO, C.—DE SANTIS, A.—STINSON, D. R.—VACCARO, U.: Graph decomposition and secret sharing schemes, J. Cryptology 8 (1995), no. 1, 39–64.10.1007/BF00204801
Search in Google Scholar Back to article
[4] BRICKELL, E. F.—STINSON, D. R.: Some improved bounds on the information rate of perfect secret sharing schemes, J. Cryptology 5 (1992), 153–166.10.1007/BF02451112
Search in Google Scholar Back to article
[5] CSIRMAZ, L.: Secret sharing schemes on graphs, Studia Sci. Math. Hungar. 44 (2007), 297–306.10.1556/sscmath.2007.1021
Search in Google Scholar Back to article
[6] _____ An impossibility result on graph secret sharing, Des.Codes Cryptogr. 53 (2009), no. 3, 195–209.10.1007/s10623-009-9304-0
Search in Google Scholar Back to article
[7] CSIRMAZ, L.—LIGETI, P.: On an infinite family of graphs with information ratio 2−1/k, Computing 85 (2009), 127–136.10.1007/s00607-009-0039-6
Search in Google Scholar Back to article
[8] _____ Secret sharing on large girth graphs, Cryptogr. Commun. (2018); https://doi.org/10.1007/s12095-018-0338-x10.1007/s12095-018-0338-x
Search in Google Scholar Back to article
[9] CSIRMAZ, L.—TARDOS, G.: Optimal information rate of secret sharing schemes on trees, IEEE Trans. Inform. Theory 59 (2013), no. 4, 2527–2630.10.1109/TIT.2012.2236958
Search in Google Scholar Back to article
[10] DEHKORDI, M. H.—SAFI, A.: The complexity of the connected graph access structure on seven participants, J. Math. Cryptol. 11 (2017), no. 1, 25–35.10.1515/jmc-2016-0017
Search in Google Scholar Back to article
[11] FARRÀS, O.—KACED, T.—MARTIN, S.—PADRÓ, C.: Improving the Linear Programming Technique in the Search for Lower Bounds in Secret Sharing, Report 2017/919,2017, Cryptology ePrint Archive, https://eprint.iacr.org/2017/919
Search in Google Scholar Back to article
[12] HARSÁNYI, K.—LIGETI, P.: Exact information ratios for secret sharing on small graphs with girth at least 5, J. Math. Cryptol. (2019) https://doi.org/10.1515/jmc-2018-002410.1515/jmc-2018-0024
Open DOI Search in Google Scholar Back to article
[13] JACKSON, W.—MARTIN, K. M.: Perfect secret sharing schemes on five participants, Des. Codes Cryptogr. 9 (1996), 233–250.10.1007/BF00189262
Search in Google Scholar Back to article
[14] SHAMIR, A.: How to share a secret, Commun. ACM 22 (1979), 612–613.10.1145/359168.359176
Open DOI Search in Google Scholar Back to article
[15] SONG, Y.—LI, Z.—LI, Y.—XIN, R.: The optimal information rate for graph access structures of nine participants, Front.Comput.Sci. 9, (2015) no. 5, 778–787.10.1007/s11704-015-3255-6
Search in Google Scholar Back to article
[16] SONG, Y.—LI, Z.—WANG, W.: The information rate of secret sharing schemes on seven participants by connected graphs. In: Recent Adv. in CSIE Vol. 4 (Z. Quian et al, eds.), Lecture Notes in Electrical Engnr. Vol. 127 (2012), pp. 637–645.10.1007/978-3-642-25769-8_90
Search in Google Scholar Back to article
[17] STINSON, D. R.: New general lower bounds on the information rate of secret sharing schemes. In: Advances in Cryptology—CRYPTO ’92, Lecture Notes in Comput. Sci. Vol. 740, 1993, pp. 168–182.10.1007/3-540-48071-4_12
Search in Google Scholar Back to article
[18] _____ Decomposition construction for secret sharing schemes, IEEE, Trans. Inform. Theory 40 (1994), no. 1, 118–125.10.1109/18.272461
Search in Google Scholar Back to article
[19] SUN, H. L.—CHEN, B. L.: Weighted decomposition construction for perfect secret sharing schemes. Comput. Math. Appl. 43 (2002), no. 6–7, 877–887.10.1016/S0898-1221(01)00328-5
Open DOI Search in Google Scholar Back to article
[20] VAN DIJK, M.: On the information rate of perfect secret sharing schemes, Des. Codes Cryptogr. 6 (1995) no. 2, 143–169.10.1007/BF01398012
Search in Google Scholar Back to article
[21] WANG, W.—LI, Z.—SONG, Y.: The optimal information rate of perfect secret sharing schemes. In: International Conference on Business Management and Electronic Information Vol. 2, IEEE, 2011, pp. 207–212.10.1109/ICBMEI.2011.5917883
Search in Google Scholar Back to article

On the Information Ratio of Graphs with Many Leaves

Abstract

Paradigm

My account