Paper 2019/597

A Candidate Access Structure for Super-polynomial Lower Bound on Information Ratio

Shahram Khazaei


The contribution vector (convec) of a secret sharing scheme is the vector of all share sizes divided by the secret size. A measure on the convec (e.g., its maximum or average) is considered as a criterion of efficiency of secret sharing schemes, which is referred to as the information ratio. 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^{\mathrm{\Omega}(n)}$, where the parameter $n$ stands for the number of participants. The best known lower bound, due to Csirmaz (1994), is $\mathrm{\Omega}(n/\log n)$. Closing this gap is a long-standing open problem in cryptology. Using a technique called \emph{substitution}, we recursively construct a family of access structures by starting from that of Csirmaz, which might be a candidate for super-polynomial information ratio. We provide support for this possibility by showing that our family has information ratio ${n^{\mathrm{\Omega}(\frac{\log n}{\log \log n})}}$, assuming the truth of a well-stated information-theoretic conjecture, called the \emph{substitution conjecture}. The substitution method is a technique for composition of access structures, similar to the so called block composition of Boolean functions, and the substitution conjecture is reminiscent of the Karchmer-Raz-Wigderson conjecture on depth complexity of Boolean functions. It emerges after introducing the notion of convec set for an access structure, a subset of $n$-dimensional real space, which includes all achievable convecs. We prove some topological properties about convec sets and raise several open problems.

Available format(s)
Publication info
Preprint. Minor revision.
secret sharinggeneral access structuresinformation ratiocommunication complexity
Contact author(s)
shahram khazaei @ gmail com
2019-06-02: received
Short URL
Creative Commons Attribution


      author = {Shahram Khazaei},
      title = {A Candidate Access Structure for Super-polynomial Lower Bound on Information Ratio},
      howpublished = {Cryptology ePrint Archive, Paper 2019/597},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.