Welcome to the resource topic for 2016/726
Title:
Local Bounds for the Optimal Information Ratio of Secret Sharing Schemes
Authors: Oriol Farràs, Jordi Ribes-González, Sara Ricci
Abstract:The information ratio of a secret sharing scheme \Sigma is the ratio between the length of the largest share and the length of the secret, and it is denoted by \sigma(\Sigma). The optimal information ratio of an access structure \Gamma is the infimum of \sigma(\Sigma) among all schemes \Sigma with access structure \Gamma, and it is denoted by \sigma(\Gamma). The main result of this work is that for every two access structures \Gamma and \Gamma', |\sigma(\Gamma)-\sigma(\Gamma')|\leq |\Gamma\cup\Gamma'|-|\Gamma\cap\Gamma'|. We prove it constructively. Given any secret sharing scheme \Sigma for \Gamma, we present a method to construct a secret sharing scheme \Sigma' for \Gamma' that satisfies that \sigma(\Sigma')\leq \sigma(\Sigma)+|\Gamma\cup\Gamma'|-|\Gamma\cap\Gamma'|. As a consequence of this result, we see that \emph{close} access structures admit secret sharing schemes with similar information ratio. We show that this property is also true for particular classes of secret sharing schemes and models of computation, like the family of linear secret sharing schemes, span programs, Boolean formulas and circuits. In order to understand this property, we also study the limitations of the techniques for finding lower bounds on the information ratio and other complexity measures. We analyze the behavior of these bounds when we add or delete subsets from an access structure.
ePrint: https://eprint.iacr.org/2016/726
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .