Laszlo Csirmaz

Tatracrypt 2007, Smolenice - Slovakia
June 22-24, 2007

Exact bounds on tree based secret sharing schemes

Abstract

In a perfect secret sharing scheme participants receive shares so that qualified subsets of the participants can recover the secret from their shares, while the total information received by all members of an unqualified subset is statistically independent of the secret. The family of the qualifies subsets of the participants is called access structure.

Given an access structure A, the efficiency of a scheme based on A is measured by the amount of information the participants must remember for each bit in the secret. The information rate of A, denoted by ρ, is the lower bound (over all possible schemes) of the maximum (over the participants) of this amount. The information rate is always ≥ 1 (for any non-trivial access structure), and can be arbitrarily large. In particular, for each n there is an access structure on an n-element set of participants which has information rate ρ ≥ n/log n. This almost linear lower bound is very probably far from the truth, which is conjectured to be exponentially large.

A special type of access structure are based on graphs. Given a graph G, the participants are the vertices of G, and the minimal qualified sets are just the edges of G. The information rate of graph based access structures has been investigated thoroughly. Some results in this area:

ρ = 1 for the complete graph K_n (Shamir)
ρ ≤ (d+1)/2 where d is the maximal degree (Stinson)
ρ ≤ n/log n for all graphs on n vertices (Erdős and Pyber)
ρ ≥ log₂ n for some graph on n vertices (Csirmaz)

The exact information rate for all graphs on at most 5 vertices has been determined, and only a couple of (sparse) infinite families of graphs were created where the information rate could be computed exactly.

The results reported here were achieved jointly with Gábor Tardos of the Rényi Institute, Hungary. We determined the exact information rate for all elements of the very first natural subclass of graphs: for trees. To state our main result we need the following

Definition: A core of the graph G is a connected subset C of the vertices such that each vertex in C has a neighbor (in G) outside of C.

With this definition we can state our result.

Theorem: Let G be a tree on n vertices, and let k be the size of the maximal core in G. Then the information rate of G is 2-1/k.

As an example, let G be a path of length at least 3. The maximal core has size 2, and it consists of the two neighbors. Thus the information rate is 2-1/2=3/2. Another example is the complete l level binary tree with 2^l-1 vertices. A core might have at most one element in each level, thus the maximal core size is l-1, and the information rate is 2-1/(l-1).

The proof that the information rate is at least 2-1/k uses information theoretic machinery: We estimate the sum of the entropies of the vertices in a core. The other side comes from a construction which uses multiple edge covering by stars.