[Resource Topic] 2018/143: Conjecturally Superpolynomial Lower Bound for Share Size

Welcome to the resource topic for 2018/143

Conjecturally Superpolynomial Lower Bound for Share Size

Authors: Shahram Khazaei


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.

ePrint: https://eprint.iacr.org/2018/143

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .