Kybernetika 60 no. 5, 553-575, 2024

Bounds on guessing numbers and secret sharing combining information theory methods

Emirhan GürpınarDOI: 10.14736/kyb-2024-5-0553

Abstract:

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.

Keywords:

Shannon entropy, information theory, linear programming, secret sharing, non-Shannon-type information inequalities, symmetries, copy lemma, entropy region, guessing games, network coding, multiple unicast, Shannon inequalities

Classification:

94A05, 94A15, 94A17, 94A62

paper.pdf

References:

  1. R. Baber, D. Christofides, A. N. Dang, E. R. Vaughan and S. A. Riis: Graph guessing games and non-Shannon information inequalities. IEEE Trans. Inform. Theory 63 (2016), 7, 4257-4267.   DOI:10.1109/TIT.2016.2628819
  2. M. Bamiloshin, A. Ben-Efraim, O. Farras and C. Padro: Common information, matroid representation, and secret sharing for matroid ports. Designs Codes Cryptogr. 89 (2021), 1, 143-166.   DOI:10.1007/s10623-020-00811-1
  3. A. Beimel: Secret-sharing schemes: A survey. In: International Conference on Coding and Cryptology, Springer 2011, pp. 11-46.   CrossRef
  4. A. Beimel, N. Livne and Carles Padro: Matroids can be far from ideal secret sharing. In: Theory of Cryptography Conference, Springer 2008, pp. 194-212.   CrossRef
  5. J. Benaloh and J. Leichter: Generalized secret sharing and monotone functions. In: Conference on the Theory and Application of Cryptography, Springer 1988, pp. 27-35.   CrossRef
  6. G. R. Blakley: Safeguarding cryptographic keys. In: Managing Requirements Knowledge, International Workshop, IEEE Computer Society 1979, pp. 313-313.   CrossRef
  7. E. F. Brickell and D. M. Davenport: On the classification of ideal secret sharing schemes. J. Cryptology 4 (1991), 2, 123-134.   DOI:10.1007/BF00196772
  8. S. Butler, M. T. Hajiaghayi, R. D. Kleinberg and T. Leighton: Hat guessing games. SIAM Rev. 51 (2009), 2, 399-413.   DOI:10.1137/080743470
  9. R. M. Capocelli, A. De Santis, L. Gargano and U. Vaccaro: On the size of shares for secret sharing schemes. J. Cryptology 6 (1993), 3, 157-167.   DOI:10.1007/BF00198463
  10. D. Christofides and K. Markstr: The guessing number of undirected graphs. Electr. J. Combin. (2011), 192-192.   CrossRef
  11. L. Csirmaz: The size of a share must be large. J. Cryptology 10 (1997), 4, 223-231.   DOI:10.1007/s001459900029
  12. R. Dougherty, Ch. Freiling and K. Zeger: Non-Shannon information inequalities in four random variables. In: arXiv preprint arXiv:1104.3602 (2011).   CrossRef
  13. O. Farras: Secret sharing schemes for ports of matroids of rank 3. Kybernetika 56 (2020), 5, 903-915.   DOI:10.1134/S1022795420080116
  14. O. Farras, T. Kaced, S. Martin and C. Padro: 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.   CrossRef
  15. O. Farras, Tarik Kaced, S. Martin and C. Padro: Improving the linear programming technique in the search for lower bounds in secret sharing. IEEE Trans. Inform. Theor 66 (2020), 11, 7088-7100.   DOI:10.1109/TIT.2020.3005706
  16. J. C. Fournier: epresentation sur un Corps d Ordre. In: Theorie des Matroides, Springer 1971, pp. 50-61.   CrossRef
  17. E. Gurpinar and A. Romashchenko: 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.   CrossRef
  18. M. Ito, A. Saito and T. Nishizeki: Secret sharing scheme realizing general access structure. In: Electronics and Communications in Japan (Part III: Fundamental Electronic Science).   CrossRef
  19. T. Ma, X. Sun and H. Yu: A new variation of hat guessing games. In: International Computing and Combinatorics Conference, Springer 2011, pp. 616-626.   CrossRef
  20. J. Martín-Farras and C. Padro: VOn secret sharing schemes, matroids and polymatroids. J. Math. Cryptol. 4 (2010), 2, 95-120.   CrossRef
  21. J. Martin and P. Rombach: Guessing Numbers and Extremal Graph Theory. In: arXiv preprint arXiv:1104.3602, 2020.   CrossRef
  22. J. R. Metcalf-Burton: 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:10.1016/j.disc.2011.01.003
  23. J. Oxley: Matroid Theory. Second edition. Oxford University Press, 2011.   CrossRef
  24. C. Padro: Lecture notes in secret sharing. In: Cryptology ePrint Archive 2012.   CrossRef
  25. C. Padro, L. Vazquez and A. Yang: Finding lower bounds on the complexity of secret sharing schemes by linear programming. Discrete Appl. Math. 161 (2013), 7-8, 1072-1084.   DOI:10.1016/j.dam.2012.10.020
  26. S. Riis: Information flows, graphs and their guessing numbers. In: Electr. J. Combinator. (2007), R44-R44.   CrossRef
  27. S. Riis: Utilising public information in network coding. General Theory Inform. Transfer Combinator. 4123 (2006), 866-897.   CrossRef
  28. S. Robinson: Why mathematicians now care about their hat color. In: The New York Times, Science Times Section, page D 5 (2001).   CrossRef
  29. P. D. Seymour: A forbidden minor characterization of matroid ports. The Quarterly J. Math. 27 (1976), 4, 407-413.   DOI:10.1093/qmath/27.4.407
  30. A. Shamir: How to share a secret. Commun. ACM 22 (1979), 11, 612-613.   DOI:10.1145/359168.359176
  31. C. E. Shannon: A mathematical theory of communication. Bell Syst. Techn. J. 27 (1948), 3, 379-423.   DOI:10.1002/j.1538-7305.1948.tb01338.x
  32. P. Vamos: On the representation of independence structures. Unpublished manuscript, 1968.   CrossRef
  33. P. Winkler: Games people don't play. 2002   CrossRef
  34. R. Wai-Ho Yeung: A first Course in Information Theory. Springer Science and Business Media, 2002.   CrossRef
  35. Z. Zhang and R. Wai-Ho Yeung: A non-Shannon-type conditional inequality of information quantities. IEEE Trans. Inform. Theory 43 (1997), 6, 1982-1986.   CrossRef
  36. Z. Zhang and R. Wai-Ho Yeung: On characterization of entropy function via information inequalities. IEEE Trans. Inform. Theory 44 (1998), 4, 1440-1452.   CrossRef