Bounds on guessing numbers and secret sharing combining information theory methods

Gürpınar, Emirhan

Kybernetika, Tome 60 (2024) no. 5, pp. 553-575

Abstract (VO)

This paper is on developing some computer-assisted proof methods involving non-classical inequalities for Shannon entropy. Two areas of the applications of information inequalities are studied: Secret sharing schemes and hat guessing games. In the former a random secret value is transformed into shares distributed among several participants in such a way that only the qualified groups of participants can recover the secret value. In the latter each participant is assigned a hat colour and they try to guess theirs while seeing only some of the others'. The aim is to maximize the probability that every player guesses correctly, the optimal probability depends on the underlying sight graph. We use for both problems the method of non-Shannon-type information inequalities going back to Z. Zhang and R. W. Yeung. We employ the linear programming technique that allows to apply new information inequalities indirectly, without even writing them down explicitly. To reduce the complexity of the problems of linear programming involved in the bounds we extensively use symmetry considerations. Using these tools, we improve lower bounds on the ratio of key size to secret size for the former problem and an upper bound for one of the ten vertex graphs related to an open question by Riis for the latter problem.

Détail

DOI : 10.14736/kyb-2024-5-0553

Classification : 94A05, 94A15, 94A17, 94A62
Keywords: Shannon entropy; non-Shannon-type information inequalities; secret sharing; linear programming; symmetries; copy lemma; entropy region; guessing games; network coding; multiple unicast; information theory; Shannon inequalities

Bibliographie

[1] Baber, R., Christofides, D., Dang, A. N., Vaughan, E. R., Riis, S. A.: Graph guessing games and non-Shannon information inequalities. IEEE Trans. Inform. Theory 63 (2016), 7, 4257-4267. | DOI | MR

[2] Bamiloshin, M., Ben-Efraim, A., Farras, O., Padro, C.: Common information, matroid representation, and secret sharing for matroid ports. Designs Codes Cryptogr. 89 (2021), 1, 143-166. | DOI | MR

[3] Beimel, A.: Secret-sharing schemes: A survey. In: International Conference on Coding and Cryptology, Springer 2011, pp. 11-46. | MR

[4] Beimel, A., Livne, N., Padro, Carles: Matroids can be far from ideal secret sharing. In: Theory of Cryptography Conference, Springer 2008, pp. 194-212. | MR

[5] Benaloh, J., Leichter, J.: Generalized secret sharing and monotone functions. In: Conference on the Theory and Application of Cryptography, Springer 1988, pp. 27-35. | MR

[6] Blakley, G. R.: Safeguarding cryptographic keys. In: Managing Requirements Knowledge, International Workshop, IEEE Computer Society 1979, pp. 313-313.

[7] Brickell, E. F., Davenport, D. M.: On the classification of ideal secret sharing schemes. J. Cryptology 4 (1991), 2, 123-134. | DOI | MR

[8] Butler, S., Hajiaghayi, M. T., Kleinberg, R. D., Leighton, T.: Hat guessing games. SIAM Rev. 51 (2009), 2, 399-413. | DOI | MR

[9] Capocelli, R. M., Santis, A. De, Gargano, L., Vaccaro, U.: On the size of shares for secret sharing schemes. J. Cryptology 6 (1993), 3, 157-167. | DOI | MR

[10] Christofides, D., Markstr, K.: The guessing number of undirected graphs. Electr. J. Combin. (2011), 192-192. | DOI | MR

[11] Csirmaz, L.: The size of a share must be large. J. Cryptology 10 (1997), 4, 223-231. | DOI | MR

[12] Dougherty, R., Freiling, Ch., Zeger, K.: Non-Shannon information inequalities in four random variables. In: arXiv preprint arXiv:1104.3602 (2011). | MR

[13] Farras, O.: Secret sharing schemes for ports of matroids of rank 3. Kybernetika 56 (2020), 5, 903-915. | DOI | MR

[14] Farras, O., Kaced, T., Martin, S., Padro, C.: Improving the linear programming technique in the search for lower bounds in secret sharing. In: Annual International Conference on the Theory and Applications of Cryptographic Techniques, Springer 2018, pp. 597-621. | MR

[15] Farras, O., Kaced, Tarik, Martin, S., Padro, C.: Improving the linear programming technique in the search for lower bounds in secret sharing. IEEE Trans. Inform. Theor 66 (2020), 11, 7088-7100. | DOI | MR

[16] Fournier, J. C.: epresentation sur un Corps d Ordre. In: Theorie des Matroides, Springer 1971, pp. 50-61. | MR

[17] Gurpinar, E., Romashchenko, A.: How to use undiscovered information inequalities: Direct applications of the copy lemma. In: IEEE International Symposium on Information Theory (ISIT), IEEE 2019, pp. 1377-1381.

[18] Ito, M., Saito, A., Nishizeki, T.: Secret sharing scheme realizing general access structure. In: Electronics and Communications in Japan (Part III: Fundamental Electronic Science). | MR

[19] Ma, T., Sun, X., Yu, H.: A new variation of hat guessing games. In: International Computing and Combinatorics Conference, Springer 2011, pp. 616-626. | MR

[20] Martín-Farras, J., Padro, C.: VOn secret sharing schemes, matroids and polymatroids. J. Math. Cryptol. 4 (2010), 2, 95-120. | MR

[21] Martin, J., Rombach, P.: Guessing Numbers and Extremal Graph Theory. In: arXiv preprint arXiv:1104.3602, 2020. | MR

[22] Metcalf-Burton, J. R.: Improved upper bounds for the information rates of the secret sharing schemes induced by the Vamos matroid. Discr. Math. 311 (2011), 8-9, 651-662. | DOI | MR

[23] Oxley, J.: Matroid Theory. Second edition. Oxford University Press, 2011. | MR

[24] Padro, C.: Lecture notes in secret sharing. In: Cryptology ePrint Archive 2012.

[25] Padro, C., Vazquez, L., Yang, A.: Finding lower bounds on the complexity of secret sharing schemes by linear programming. Discrete Appl. Math. 161 (2013), 7-8, 1072-1084. | DOI | MR

[26] Riis, S.: Information flows, graphs and their guessing numbers. In: Electr. J. Combinator. (2007), R44-R44. | MR

[27] Riis, S.: Utilising public information in network coding. General Theory Inform. Transfer Combinator. 4123 (2006), 866-897.

[28] Robinson, S.: Why mathematicians now care about their hat color. In: The New York Times, Science Times Section, page D 5 (2001).

[29] Seymour, P. D.: A forbidden minor characterization of matroid ports. The Quarterly J. Math. 27 (1976), 4, 407-413. | DOI | MR

[30] Shamir, A.: How to share a secret. Commun. ACM 22 (1979), 11, 612-613. | DOI | MR

[31] Shannon, C. E.: A mathematical theory of communication. Bell Syst. Techn. J. 27 (1948), 3, 379-423. | DOI | MR | Zbl

[32] Vamos, P.: On the representation of independence structures. Unpublished manuscript, 1968.

[33] Winkler, P.: Games people don't play. 2002

[34] Yeung, R. Wai-Ho: A first Course in Information Theory. Springer Science and Business Media, 2002. | MR

[35] Zhang, Z., Yeung, R. Wai-Ho: A non-Shannon-type conditional inequality of information quantities. IEEE Trans. Inform. Theory 43 (1997), 6, 1982-1986. | DOI | MR

[36] Zhang, Z., Yeung, R. Wai-Ho: On characterization of entropy function via information inequalities. IEEE Trans. Inform. Theory 44 (1998), 4, 1440-1452. | DOI | MR