Paper 2016/726

Local Bounds for the Optimal Information Ratio of Secret Sharing Schemes

Oriol Farràs, Jordi Ribes-González, and 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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
secret sharing
Contact author(s)
oriol farras @ urv cat
History
2018-05-24: last of 2 revisions
2016-07-27: received
See all versions
Short URL
https://ia.cr/2016/726
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/726,
      author = {Oriol Farràs and Jordi Ribes-González and Sara Ricci},
      title = {Local Bounds for the Optimal Information Ratio of Secret Sharing Schemes},
      howpublished = {Cryptology ePrint Archive, Paper 2016/726},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/726}},
      url = {https://eprint.iacr.org/2016/726}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.