Secret Sharing and Non-Shannon Information Inequalities

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

Marten van Dijk

Raymond W. Yeung, Zhen Zhang

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.

Jessica Ruth Metcalf-Burton

Many open questions in secret sharing ask about the information rate of a particular access structure or class of access structures. Here we improve the best known upper bounds on the information rates of the access structures induced by the Vamos matroid from 10/11 to 8/9 for V1 and from 9/10 to 17/19 for V6. The method we introduce to obtain the bound for V6 can be generalized and applied to all other known 4-variable non-Shannon information inequalities. We also find the exact information rates for the infinitely many minor-minimal, non-matroid-related access structures whose rates were not previously known. On the topic of information inequalities, we show that the Ingleton inequality holds under certain independence assumptions and use this formulation to get a new proof of the Zhang-Yeung non-Shannon inequality.

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