Welcome to the resource topic for 2023/289
Title:
Lower-Bounds for Secret-Sharing Schemes for k-Hypergraphs
Authors: Amos Beimel
Abstract:A secret-sharing scheme enables a dealer, holding a secret string, to distribute shares to parties such that only pre-defined authorized subsets of parties can reconstruct the secret. The collection of authorized sets is called an access structure. There is a huge gap between the best known upper-bounds on the share size of a secret-sharing scheme realizing an arbitrary access structure and the best known lower-bounds on the size of these shares. For an arbitrary n-party access structure, the best known upper-bound on the share size is 2^{O(n)}. On the other hand, the best known lower-bound on the total share size is much smaller, i.e., \Omega(n^2/\log (n)) [Csirmaz, \emph{Studia Sci. Math. Hungar.}]. This lower-bound was proved more than 25 years ago and no major progress was made since.
In this paper, we study secret-sharing schemes for k-hypergraphs, i.e., for access structure where all minimal authorized sets are of size exactly k (however, unauthorized sets can be larger). We consider the case where k is small, i.e., constant or at most \log (n). The trivial upper-bound for these access structures is O(k\cdot \binom{n}{k}) and this can be slightly improved. If there were efficient secret-sharing schemes for such k-hypergraphs (e.g., 2-hypergraphs or 3-hypergraphs), then we would be able to construct secret-sharing schemes for arbitrary access structure that are better than the best known schemes. Thus, understanding the share size required for k-hypergraphs is important. Prior to our work, the best known lower-bound for these access structures was \Omega(n \log (n)), which holds already for graphs (i.e., 2-hypergraphs).
We improve this lower-bound, proving a lower-bound of \Omega(n^{1-1/(k-1)}/k) for some explicit k-hypergraphs, where 3 \leq k \leq \log (n). For example, for 3-hypergraphs we prove a lower-bound of \Omega(n^{3/2}). For \log (n)-hypergraphs, we prove a lower-bound of \Omega(n^{2}/\log (n)), i.e., we show that the lower-bound of Csirmaz holds already when all minimal authorized sets are of size \log (n). Our proof is simple and shows that the lower-bound of Csirmaz holds for a simple variant of the access structure considered by Csirmaz.
ePrint: https://eprint.iacr.org/2023/289
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 .