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

Lecture notes in computer science

Secret Sharing, Rank Inequalities and Information Inequalities

Sebastià Martı́n, Carles Padró, Yang An

Published Jan 1, 2013• 12 citations
Publisher
DOI
10.1007/978-3-642-40084-1_16

Related papers

Secret Sharing and Non-Shannon Information Inequalities

Amos Beimel, Ilan Orlov

Lecture notes in computer science•Jan 1, 2009•18 citations

More information theoretical inequalities to be used in secret sharing?

Marten van Dijk

Information Processing Letters•Jul 1, 1997•7 citations

Secret Sharing, Rank Inequalities, and Information Inequalities

Sebastià Martı́n, Carles Padró, Yang An

Beimel and Orlov proved that all information inequalities on four or five variables, together with all information inequalities on more than five variables that are known to date, provide lower bounds on the size of the shares in secret sharing schemes that are at most linear on the number of participants. We present here another two negative results about the power of information inequalities in the search for lower bounds in secret sharing. First, we prove that all information inequalities on a bounded number of variables can only provide lower bounds that are polynomial on the number of participants. Second, we prove that the rank inequalities that are derived from the existence of two common informations can provide only lower bounds that are at most cubic in the number of participants.

IEEE Transactions on Information Theory•Nov 12, 2015•16 citations

Abelian sharing, common informations, and linear rank inequalities

Carolina Mejía, J. Andrés Montoya

Abstract Dougherty et al. introduced the common information (CI) method as a method to produce non-Shannon inequalities satisfied by linear random variables, which are called linear rank inequalities. This method is based on the fact that linear random variables have CI. Dougerthy et al. asked whether this method is complete, in the sense that it can be used to produce all linear rank inequalities. We study this question, and we attack it using the theory of secret sharing schemes. To this end, we introduce the notions of Abelian secret sharing scheme and Abelian capacity. We prove that: If there exists an access structure whose Abelian capacity is smaller than its linear capacity, then the CI method is not complete. We investigate the existence of such an access structure.

Journal of Mathematical Cryptology•Jan 1, 2022•0 citations

An Information-theoretic Treatment Of Secret Sharing Schemes

Renato M. Capocelli, Alfredo De Santis, Luisa Gargano +1 more

IEEE International Symposium on Information Theory (ISIT)•Aug 24, 2005•0 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
Beimel and Orlov proved that all information inequalities on four or five variables, together with all information inequalities on more than five variables that are known to date, provide lower bounds on the size of the shares in secret sharing schemes that are at most linear on the number of participants. We present here another two negative results about the power of information inequalities in the search for lower bounds in secret sharing. First, we prove that all information inequalities on a bounded number of variables can only provide lower bounds that are polynomial on the number of participants. Second, we prove that the rank inequalities that are derived from the existence of two common informations can provide only lower bounds that are at most cubic in the number of participants.
Abstract Dougherty et al. introduced the common information (CI) method as a method to produce non-Shannon inequalities satisfied by linear random variables, which are called linear rank inequalities. This method is based on the fact that linear random variables have CI. Dougerthy et al. asked whether this method is complete, in the sense that it can be used to produce all linear rank inequalities. We study this question, and we attack it using the theory of secret sharing schemes. To this end, we introduce the notions of Abelian secret sharing scheme and Abelian capacity. We prove that: If there exists an access structure whose Abelian capacity is smaller than its linear capacity, then the CI method is not complete. We investigate the existence of such an access structure.
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.