Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2201.11656 · IEEE International Symposium on Information Theory (ISIT)

Symmetries in Linear Programming for Information Inequalities

Emirhan Gürpınar

Published Jun 26, 2022• 1 citation
arXivHTMLPDF

Abstract

Secret sharing is a central topic in information-theoretical cryptography. In a secret sharing scheme a random secret is distributed among participants so that only the qualified subsets of parties can recover the secret. In this paper we improve previously known [13] lower bounds on the size of the largest share for several specific access structures. Our approach is based on non-Shannon-type information inequalities. We employ the linear programming (LP) technique that permits to apply new information inequalities indirectly. To reduce computational complexity of the involved linear programs we extensively use symmetry considerations.

DOI
10.1109/isit50566.2022.9834471

Related papers

Bounds on guessing numbers and secret sharing combining information theory methods

Emirhan Gürpınar

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.

arXiv:2310.09232•Kybernetika•Oct 17, 2024•0 citations

Improving the Linear Programming Technique in the Search for Lower Bounds in Secret Sharing

Oriol Farràs, Tarik Kaced, Sebastià Martín Mollevi +1 more

We present a new improvement in the linear programming technique to derive lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new technique makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on 5 participants and all graph-based access structures on 6 participants. In addition, new lower bounds are presented also for some small matroid ports and, in particular, the optimal information ratios of the linear secret sharing schemes for the ports of the Vamos matroid are determined.

IEEE Transactions on Information Theory•Jun 29, 2020•16 citations

Finding Lower Bounds on the Complexity of Secret Sharing Schemes by Linear Programming.

Carles Padró, Leonor Vázquez, Yang An

Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants. By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.

•Jan 1, 2012•0 citations

How to Use Undiscovered Information Inequalities: Direct Applications of the Copy Lemma

Emirhan Gürpınar, Andrei Romashchenko

We discuss linear programming techniques that help to deduce corollaries of non-classical inequalities for Shannon's entropy. We focus on direct applications of the copy lemma. These applications involve implicitly some (known or unknown) non-classical universal inequalities for Shannon's entropy, though we do not derive these inequalities explicitly. To reduce the computational complexity of these problems, we extensively use symmetry considerations. We present two examples of use of these techniques: we provide a reduced size formal inference of the best known bound for the Ingleton score (originally proven by Dougherty et al. with explicitly derived non-Shannon type inequalities), and improve the lower bound for the optimal information ratio of the secret sharing scheme for an access structure based on the Vámos matroid.

arXiv:1901.07476•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2019•19 citations

Secret Sharing and Non-Shannon Information Inequalities

Amos Beimel, Ilan Orlov

The known secret-sharing schemes for most access structures are not efficient; even for a one-bit secret the length of the shares in the schemes is 2O(n), wherenis the number of participants in the access structure. It is a long standing open problem to improve these schemes or prove that they cannot be improved. The best known lower bound is by Csirmaz, who proved that there exist access structures withnparticipants such that the size of the share of at least one party isn/logntimes the secret size. Csirmaz's proof uses Shannon information inequalities, which were the only information inequalities known when Csirmaz published his result. On the negative side, Csirmaz proved that by only using Shannon information inequalities one cannot prove a lower bound of ω(n) on the share size. In the last decade, a sequence of non-Shannon information inequalities were discovered. In fact, it was proved that there are infinity many independent information inequalities even in four variables. This raises the hope that these inequalities can help in improving the lower bounds beyondn. However, we show that any information inequality with four or five variables cannot prove a lower bound of ω(n) on the share size. In addition, we show that the same negative result holds for all information inequalities with more than five variables that are known to date.

IEEE Transactions on Information Theory•Sep 1, 2011•30 citations

New bounds on the information rate of secret sharing schemes

Carlo Blundo, Alfredo De Santis, Antonio Giorgio Gaggia +1 more

/spl acute/A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. We derive new limitations on the information rate of secret sharing schemes, that measures how much information is being distributed as shares as compared to the size of the secret key, and the average information rate, that is the ratio between the secret size and the arithmetic mean of the size of the shares. By applying the substitution technique, we are able to construct many new examples of access structures where the information rate is bounded away from 1. The substitution technique is a method used to obtain a new access structure by replacing a participant in a previous structure with a new access structure.>

IEEE Transactions on Information Theory•Mar 1, 1995•30 citations
Secret sharing is a central topic in information-theoretical cryptography. In a secret sharing scheme a random secret is distributed among participants so that only the qualified subsets of parties can recover the secret. In this paper we improve previously known [13] lower bounds on the size of the largest share for several specific access structures. Our approach is based on non-Shannon-type information inequalities. We employ the linear programming (LP) technique that permits to apply new information inequalities indirectly. To reduce computational complexity of the involved linear programs we extensively use symmetry considerations.
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.
We present a new improvement in the linear programming technique to derive lower bounds on the information ratio of secret sharing schemes. We obtain non-Shannon-type bounds without using information inequalities explicitly. Our new technique makes it possible to determine the optimal information ratio of linear secret sharing schemes for all access structures on 5 participants and all graph-based access structures on 6 participants. In addition, new lower bounds are presented also for some small matroid ports and, in particular, the optimal information ratios of the linear secret sharing schemes for the ports of the Vamos matroid are determined.
Optimizing the maximum, or average, length of the shares in relation to the length of the secret for every given access structure is a difficult and long-standing open problem in cryptology. Most of the known lower bounds on these parameters have been obtained by implicitly or explicitly using that every secret sharing scheme defines a polymatroid related to the access structure. The best bounds that can be obtained by this combinatorial method can be determined by using linear programming, and this can be effectively done for access structures on a small number of participants. By applying this linear programming approach, we improve some of the known lower bounds for the access structures on five participants and the graph access structures on six participants for which these parameters were still undetermined. Nevertheless, the lower bounds that are obtained by this combinatorial method are not tight in general. For some access structures, they can be improved by adding to the linear program non-Shannon information inequalities as new constraints. We obtain in this way new separation results for some graph access structures on eight participants and for some ports of non-representable matroids. Finally, we prove that, for two access structures on five participants, the combinatorial lower bound cannot be attained by any linear secret sharing scheme.
We discuss linear programming techniques that help to deduce corollaries of non-classical inequalities for Shannon's entropy. We focus on direct applications of the copy lemma. These applications involve implicitly some (known or unknown) non-classical universal inequalities for Shannon's entropy, though we do not derive these inequalities explicitly. To reduce the computational complexity of these problems, we extensively use symmetry considerations. We present two examples of use of these techniques: we provide a reduced size formal inference of the best known bound for the Ingleton score (originally proven by Dougherty et al. with explicitly derived non-Shannon type inequalities), and improve the lower bound for the optimal information ratio of the secret sharing scheme for an access structure based on the Vámos matroid.
The known secret-sharing schemes for most access structures are not efficient; even for a one-bit secret the length of the shares in the schemes is 2O(n), wherenis the number of participants in the access structure. It is a long standing open problem to improve these schemes or prove that they cannot be improved. The best known lower bound is by Csirmaz, who proved that there exist access structures withnparticipants such that the size of the share of at least one party isn/logntimes the secret size. Csirmaz's proof uses Shannon information inequalities, which were the only information inequalities known when Csirmaz published his result. On the negative side, Csirmaz proved that by only using Shannon information inequalities one cannot prove a lower bound of ω(n) on the share size. In the last decade, a sequence of non-Shannon information inequalities were discovered. In fact, it was proved that there are infinity many independent information inequalities even in four variables. This raises the hope that these inequalities can help in improving the lower bounds beyondn. However, we show that any information inequality with four or five variables cannot prove a lower bound of ω(n) on the share size. In addition, we show that the same negative result holds for all information inequalities with more than five variables that are known to date.
/spl acute/A secret sharing scheme permits a secret to be shared among participants in such a way that only qualified subsets of participants can recover the secret, but any nonqualified subset has absolutely no information on the secret. We derive new limitations on the information rate of secret sharing schemes, that measures how much information is being distributed as shares as compared to the size of the secret key, and the average information rate, that is the ratio between the secret size and the arithmetic mean of the size of the shares. By applying the substitution technique, we are able to construct many new examples of access structures where the information rate is bounded away from 1. The substitution technique is a method used to obtain a new access structure by replacing a participant in a previous structure with a new access structure.>