Paper 2013/082

Secret Sharing, Rank Inequalities, and Information Inequalities

Sebastia Martin, Carles Padro, and An Yang


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. And 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.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in CRYPTO 2013
Secret sharingInformation inequalitiesRank inequalitiesPolymatroid.
Contact author(s)
carles padro @ upc edu
2015-11-27: last of 3 revisions
2013-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sebastia Martin and Carles Padro and An Yang},
      title = {Secret Sharing, Rank Inequalities, and Information Inequalities},
      howpublished = {Cryptology ePrint Archive, Paper 2013/082},
      year = {2013},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.