CWI Cryptology Group

Abstract: Optimizing the length of the shares in secret sharing schemes is a difficult open problem. There is a huge gap between the best known lower and upper bounds. The only available technique to obtain lower bounds combines polymatroids, linear programming and information inequalities. Following the works by Csirmaz (1994) and Beimel and Orlov (2008), we analyze here the limitations of this technique.
Csirmaz proved that the best lower bounds that can be obtained by using only the basic Shannon inequalities are at most linear on the number of participants. Beimel and Orlov extended that result to all information inequalities on four or five variables, together with all information inequalities on more than five variables that are known to date. In this work, we prove that all (known or unknown) information inequalities on a bounded number of variables only can provide lower bounds that are polynomial on the number of participants. Our result is proved by finding solutions with small value for the involved linear programs. A simple family of uniform Boolean polymatroids is used in the search of such solutions.