Paper 2023/289
Lower Bounds for SecretSharing Schemes for kHypergraphs
Abstract
A secretsharing scheme enables a dealer, holding a secret string, to distribute shares to parties such that only predefined 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 secretsharing 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 has been made since. In this paper, we study secretsharing schemes for $k$hypergraphs, i.e., for access structures 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(n\cdot \binom{n1}{k1})$ and this can be slightly improved. If there were efficient secretsharing schemes for such $k$hypergraphs (e.g., $2$hypergraphs or $3$hypergraphs), then we would be able to construct secretsharing schemes for arbitrary access structures 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^{21/(k1)}/k)$ on the total share size 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. Using our results, we prove a near quadratic separation between the required share size for realizing an explicit access structure and the monotone circuit size describing the access structure,i.e., the share size in $\Omega(n^2/\log(n))$ and the monotone circuit size is $O(n\log(n))$ (where the circuit has depth $3$).
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Published elsewhere. ITC 2023
 DOI
 10.4230/LIPIcs.ITC.2023.16
 Keywords
 Secret SharingShare SizeHypergraphsMonotone Circuits
 Contact author(s)
 amos beimel @ gmail com
 History
 20230731: last of 3 revisions
 20230226: received
 See all versions
 Short URL
 https://ia.cr/2023/289
 License

CC BY
BibTeX
@misc{cryptoeprint:2023/289, author = {Amos Beimel}, title = {Lower Bounds for SecretSharing Schemes for kHypergraphs}, howpublished = {Cryptology ePrint Archive, Paper 2023/289}, year = {2023}, doi = {10.4230/LIPIcs.ITC.2023.16}, note = {\url{https://eprint.iacr.org/2023/289}}, url = {https://eprint.iacr.org/2023/289} }