Bounds on guessing numbers and secret sharing combining information theory methods

Emirhan Gürpınar

Kybernetika (2024)

  • Volume: 60, Issue: 5, page 553-575
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Gürpınar, Emirhan. "Bounds on guessing numbers and secret sharing combining information theory methods." Kybernetika 60.5 (2024): 553-575. <http://eudml.org/doc/299727>.

@article{Gürpınar2024,
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.},
author = {Gürpınar, Emirhan},
journal = {Kybernetika},
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},
language = {eng},
number = {5},
pages = {553-575},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Bounds on guessing numbers and secret sharing combining information theory methods},
url = {http://eudml.org/doc/299727},
volume = {60},
year = {2024},
}

TY - JOUR
AU - Gürpınar, Emirhan
TI - Bounds on guessing numbers and secret sharing combining information theory methods
JO - Kybernetika
PY - 2024
PB - Institute of Information Theory and Automation AS CR
VL - 60
IS - 5
SP - 553
EP - 575
AB - 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.
LA - eng
KW - 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
UR - http://eudml.org/doc/299727
ER -

References

top
  1. Baber, R., Christofides, D., Dang, A. N., Vaughan, E. R., Riis, S. A., , IEEE Trans. Inform. Theory 63 (2016), 7, 4257-4267. MR3666958DOI
  2. Bamiloshin, M., Ben-Efraim, A., Farras, O., Padro, C., , Designs Codes Cryptogr. 89 (2021), 1, 143-166. MR4202698DOI
  3. Beimel, A., Secret-sharing schemes: A survey., In: International Conference on Coding and Cryptology, Springer 2011, pp. 11-46. MR2834691
  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. MR2494143
  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. MR1046379
  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., , J. Cryptology 4 (1991), 2, 123-134. MR1062240DOI
  8. Butler, S., Hajiaghayi, M. T., Kleinberg, R. D., Leighton, T., , SIAM Rev. 51 (2009), 2, 399-413. MR2505586DOI
  9. Capocelli, R. M., Santis, A. De, Gargano, L., Vaccaro, U., , J. Cryptology 6 (1993), 3, 157-167. MR1243646DOI
  10. Christofides, D., Markstr, K., 10.37236/679, Electr. J. Combin. (2011), 192-192. MR2836827DOI10.37236/679
  11. Csirmaz, L., , J. Cryptology 10 (1997), 4, 223-231. MR1476611DOI
  12. Dougherty, R., Freiling, Ch., Zeger, K., Non-Shannon information inequalities in four random variables., In: arXiv preprint arXiv:1104.3602 (2011). MR2321860
  13. Farras, O., , Kybernetika 56 (2020), 5, 903-915. MR4187779DOI
  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. MR3794799
  15. Farras, O., Kaced, Tarik, Martin, S., Padro, C., , IEEE Trans. Inform. Theor 66 (2020), 11, 7088-7100. MR4173629DOI
  16. Fournier, J. C., epresentation sur un Corps d Ordre., In: Theorie des Matroides, Springer 1971, pp. 50-61. MR0376399
  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). MR1048477
  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. MR2875082
  20. Martín-Farras, J., Padro, C., VOn secret sharing schemes, matroids and polymatroids., J. Math. Cryptol. 4 (2010), 2, 95-120. MR2729351
  21. Martin, J., Rombach, P., Guessing Numbers and Extremal Graph Theory., In: arXiv preprint arXiv:1104.3602, 2020. MR4441094
  22. Metcalf-Burton, J. R., , Discr. Math. 311 (2011), 8-9, 651-662. MR2774219DOI
  23. Oxley, J., Matroid Theory. Second edition., Oxford University Press, 2011. MR2849819
  24. Padro, C., Lecture notes in secret sharing., In: Cryptology ePrint Archive 2012. 
  25. Padro, C., Vazquez, L., Yang, A., , Discrete Appl. Math. 161 (2013), 7-8, 1072-1084. MR3030592DOI
  26. Riis, S., Information flows, graphs and their guessing numbers., In: Electr. J. Combinator. (2007), R44-R44. MR2320600
  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., , The Quarterly J. Math. 27 (1976), 4, 407-413. MR0429611DOI
  30. Shamir, A., , Commun. ACM 22 (1979), 11, 612-613. MR0549252DOI
  31. Shannon, C. E., , Bell Syst. Techn. J. 27 (1948), 3, 379-423. Zbl1154.94303MR0026286DOI
  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. MR2042182
  35. Zhang, Z., Yeung, R. Wai-Ho, 10.1109/18.641561, IEEE Trans. Inform. Theory 43 (1997), 6, 1982-1986. MR1481054DOI10.1109/18.641561
  36. Zhang, Z., Yeung, R. Wai-Ho, 10.1109/18.681320, IEEE Trans. Inform. Theory 44 (1998), 4, 1440-1452. MR1665794DOI10.1109/18.681320

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.