We consider the problem of threshold secret sharing in
groups with hierarchical structure: a subset of
participants is authorized if it has at least k_0
members from the highest level, as well as at least
k_1 members from the two highest levels and so
forth. Such problems occur in settings where the
participants differ in their authority or level of
confidence and the presence of higher-level participants
is imperative to allow the recovery of the common secret.
Even though secret sharing in hierarchical groups has been
studied extensively in the past, none of the proposed solutions
addresses the simple setting that was described above.
We present a secret sharing
scheme for this problem that is both perfect and ideal. As in Shamir's scheme,
the secret is represented as the free coefficient of some
polynomial. The novelty of our scheme is the usage of
polynomial derivatives in order to generate lesser
shares for participants of lower levels. Consequently,
our scheme uses Birkhoff interpolation, i.e., the
construction of a polynomial according to an unstructured
set of point and derivative values.
Unfortunately, Birkhoff interpolation problems are not
always well posed.
Hence, a substantial part of our
study is dedicated to strategies that guarantee
well-posedness. Combining our
results with a duality result of A. Gal
regarding monotone span programs, we infer that the
closely related hierarchical
threshold access
structures that were studied by Simmons and Brickell
are also ideal. An explicit ideal scheme for
those problems is presented.