Bounds on Guessing Numbers and Secret Sharing - LIRMM - Laboratoire d’Informatique, de Robotique et de Microélectronique de Montpellier Accéder directement au contenu
Pré-Publication, Document De Travail Année : 2023

Bounds on Guessing Numbers and Secret Sharing

Résumé

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
BGNSS.pdf (419.8 Ko) Télécharger le fichier
Origine Fichiers produits par l'(les) auteur(s)
Licence

Dates et versions

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

Licence

Identifiants

  • HAL Id : lirmm-04238195 , version 1

Citer

Emirhan Gürpınar. Bounds on Guessing Numbers and Secret Sharing: Combining Information Theory Methods. 2023. ⟨lirmm-04238195v1⟩
31 Consultations
49 Téléchargements

Partager

Gmail Mastodon Facebook X LinkedIn More