Paper 2019/597

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

Shahram Khazaei

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. Minor revision.
Keywords
secret sharinggeneral access structuresinformation ratiocommunication complexity
Contact author(s)
shahram khazaei @ gmail com
History
2019-06-02: received
Short URL
https://ia.cr/2019/597
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/597,
      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{https://eprint.iacr.org/2019/597}},
      url = {https://eprint.iacr.org/2019/597}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.