**Bounds on the Information Ratios of Secret Sharing Schemes for Close Access Structures**

*Oriol Farrąs and Jordi Ribes-Gonzįlez and Sara Ricci*

**Abstract: **The information ratio of a secret sharing scheme $\Sigma$ measures the size of the largest share of the scheme, and is denoted by $\sigma(\Sigma)$. The optimal information ratio of an access structure $\Gamma$ is the infimum of $\sigma(\Sigma)$ among all schemes $\Sigma$ for $\Gamma$, and 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'|$. As a consequence of this result, we see that close access structures admit secret sharing schemes with similar information ratio. We show that this property is also true for particular families 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

**Category / Keywords: **foundations / secret sharing

**Date: **received 22 Jul 2016, last revised 22 Jul 2016

**Contact author: **oriol farras at urv cat

**Available format(s): **PDF | BibTeX Citation

**Version: **20160727:174800 (All versions of this report)

**Short URL: **ia.cr/2016/726

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]