Paper 2019/597
A Candidate Access Structure for Superpolynomial 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 longstanding 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 superpolynomial 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 wellstated informationtheoretic 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 KarchmerRazWigderson 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)
 Category
 Foundations
 Publication info
 Preprint. Minor revision.
 Keywords
 secret sharinggeneral access structuresinformation ratiocommunication complexity
 Contact author(s)
 shahram khazaei @ gmail com
 History
 20190602: received
 Short URL
 https://ia.cr/2019/597
 License

CC BY
BibTeX
@misc{cryptoeprint:2019/597, author = {Shahram Khazaei}, title = {A Candidate Access Structure for Superpolynomial 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} }