Tatracrypt 2007, Smolenice - Slovakia
June 22-24, 2007
Slides (pdf) |
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:
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
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.