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.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 TheorySep 1, 201130 citations

Some inequalities satisfied by the quantities of information of Fisher and Shannon

Aart Johannes Stam

Information and ControlJun 1, 1959705 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.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.07476IEEE International Symposium on Information Theory (ISIT)Jul 1, 201919 citations

Secret Sharing and Non-Shannon Information Inequalities

Amos Beimel, Ilan Orlov

Lecture notes in computer scienceJan 1, 200918 citations

Some applications of matrix inequalities in Rényi entropy

Hadi Reisizadeh, Seyed Mahmoud Manjegani

The R{é}nyi entropy is one of the important information measures that generalizes Shannon's entropy. The quantum R{é}nyi entropy has a fundamental role in quantum information theory, therefore, bounding this quantity is of vital importance. Another important quantity is R{é}nyi relative entropy on which R{é}nyi generalization of the conditional entropy, and mutual information are defined based. Thus, finding lower bound for R{é}nyi relative entropy is our goal in this paper. We use matrix inequalities to prove new bounds on the entropy of type $β$ , R{é}nyi entropy.The R{é}nyi entropy is one of the important information measures that generalizes Shannon's entropy. The quantum R{é}nyi entropy has a fundamental role in quantum information theory, therefore, bounding this quantity is of vital importance. Another important quantity is R{é}nyi relative entropy on which R{é}nyi generalization of the conditional entropy, and mutual information are defined based. Thus, finding lower bound for R{é}nyi relative entropy is our goal in this paper. We use matrix inequalities to prove new bounds on the entropy of type $β$, R{é}nyi entropy.

arXiv:1608.03362Aug 11, 20160 citations

β

, R{é}nyi entropy.