Bounds on Guessing Numbers and Secret Sharing - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Access content directly
Preprints, Working Papers, ... Year : 2023

Bounds on Guessing Numbers and Secret Sharing

Emirhan Gürpınar
  • Function : Author
  • PersonId : 1216314


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.
Fichier principal
Vignette du fichier
journal-long.pdf (420.01 Ko) Télécharger le fichier
Origin : Files produced by the author(s)

Dates and versions

lirmm-04238195 , version 1 (12-10-2023)
lirmm-04238195 , version 2 (18-10-2023)


  • HAL Id : lirmm-04238195 , version 2


Emirhan Gürpınar. Bounds on Guessing Numbers and Secret Sharing: Combining Information Theory Methods. 2023. ⟨lirmm-04238195v2⟩
27 View
41 Download


Gmail Facebook X LinkedIn More