Linear Secret-Sharing Schemes for $k$-uniform access structures

Abstract

A {\it $k$-uniform hypergraph} $\mathcal{H}=(V,E)$ consists of a set $V$ of vertices and a set $E$ of hyperedges ($k$-hyperedges), which is a family of $k$-subsets of $V$. A {\it forbidden $k$-homogeneous (or forbidden $k$-hypergraph)} access structure $\mathcal{A}$ is represented by a $k$-uniform hypergraph $\mathcal{H}=(V,E)$ and has the following property: a set of vertices (participants) can reconstruct the secret value from their shares in the secret sharing scheme if they are connected by a $k$-hyperedge or their size is at least $k+1$. A forbidden $k$-homogeneous access structure has been studied by many authors under the terminology of $k$-uniform access structures. In this paper, we provide efficient constructions on the total share size of linear secret sharing schemes for sparse and dense $k$-uniform access structures for a constant $k$ using the hypergraph decomposition technique and the monotone span programs.

25 pages