**Conjecturally Superpolynomial Lower Bound for Share Size**

*Shahram Khazaei*

**Abstract: **Information ratio, which measures the maximum/average share size per shared bit, is a criterion of efficiency of a secret sharing scheme. It is generally believed that there exists a family of access structures such that the information ratio of any secret sharing scheme realizing it is $2^{\Omega(n)}$, where the parameter $n$ stands for the number of participants. The best known lower bound, due to Csirmaz (1994), is $\Omega(n/\log n)$. Closing this gap is a long-standing open problem in cryptology.

In this paper, using a technique called \emph{substitution}, we recursively construct a family of access structures having information ratio $n^{\frac{\log n}{\log \log n}}$, assuming a well-stated information-theoretic conjecture is true. Our conjecture emerges after introducing the notion of \emph{convec set} for an access structure, a subset of $n$-dimensional real space. We prove some topological properties about convec sets and raise several open problems.

**Category / Keywords: **secret sharing, information-theory

**Date: **received 7 Feb 2018, last revised 14 Feb 2018

**Contact author: **shahram khazaei at gmail com

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

**Version: **20180214:121414 (All versions of this report)

**Short URL: **ia.cr/2018/143

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

[ Cryptology ePrint archive ]