IACR News item: 27 February 2023
Amos Beimel
ePrint Report
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.
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.
Additional news items may be found on the IACR news page.