Welcome to the resource topic for 2019/597
Title:
A Candidate Access Structure for Super-polynomial Lower Bound on Information Ratio
Authors: 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.
ePrint: https://eprint.iacr.org/2019/597
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 .