Study Group: Secret Sharing and Access Structures

The study group presented by Enrique and Emmanuela concerned two papers about secret sharing. For the uninitiated, secret sharing schemes ensure that a secret value is distributed into shares among a set of n users, and only authorised sets of users can reconstruct the secret from their shares, whereas any forbidden set cannot obtain any information at all about the secret.

The first paper by Farràs et al. Linear threshold multisecret sharing schemes (ICITS '09) investigates linear threshold multisecret sharing schemes, and multithreshold access structures. In a multisecret sharing scheme, many secret values are distributed among a set of users, and there may be a different access structure for each secret. In a multithreshold access structure, for every subset P of k users, there is a secret key that can only be computed when at least t of them combine their secret information. Qualified sets for the secret associated to P are those with at least t users in P, while every set with at most w users with less than t of them in P is a forbidden set. Schemes are referred to as (w,t,k,n) schemes to reflect these definitions. The case k=n corresponds to threshold secret sharing schemes introduced independently by Shamir and Blakley.
Using linear algebraic techniques, the paper gives a new general lower bound for the randomness of threshold multisecret sharing schemes, please refer to the paper for full details of the bounds and proofs. Building on previous work, the authors present a linear construction of optimal threshold multisecret scharing schemes for the case t=2, k=3 and 1 ≤ w ≤ n-2. They also present a general construction of multithreshold schemes for all possible values of the system parameters (w,t,k,n), which in general are not optimal.

The second paper is by Beimel et al. Secret Sharing Schemes for Very Dense Graphs (CRYPTO '12), which considers access structures based on graphs. If the users are represented by vertices of a graph G, a secret sharing scheme realises a graph if a subset of participants can compute the secret if they have an edge in G, otherwise they can get no information about the secret. Dense graphs are graphs that have - e edges for e « n² (where n is number of vertices).
Every graph access structure can be realized by a (linear) scheme in which the total share size is O(n² / log n). The best lower bound for the total share size required to realise a graph access structure by a general secret sharing scheme is Ω(n log n), and for linear schemes this is Ω(n^3/2). "Hard" graphs require total share size of Ω(n² / polylog n), and the paper shows that it is not possible for "hard" graphs to be very dense. The main result is that if a graph has - n^1+β edges for some 0 ≤ β ≤ 1, then it can be realized by a secret sharing scheme in which the total share size is Õ(n^{5/4 + 3β/4}) (where the Õ notation ignores polylog factors), and this scheme is linear. If β is a constant smaller than 1, the total share size is « n², and as a result these are not "hard" graphs. If β < 1/3 then the share size is o(n^3/2), and as a result these graphs are easier than the (sparse) graphs used to prove lower bounds in previous work.
Other previous work showed that a connected graph has an ideal scheme (where the total share size is n times the size of the secret) iff the graph is a complete multipartite graph. In order to construct schemes realising very dense graphs, the authors first realize (give shares) and remove certain subsets of the vertices using stars and bipartite subgraphs, until the remaining vertices can be covered by a sequence of subgraphs, G₁, ..., G_r, where each is a disjoint union of complete multipartite graphs (cliques specifically). For every i the secret is shared in G_i using ideal secret sharing schemes (Shamir) in each clique of G_i. The techniques used in the paper require considerable introduction, so the interested reader is referred to the full papers for details.